Which is computed faster, $a^b$ or $\log_a c$ or $\sqrt[b]{c}$? $a$, $b$ and $c$ are positive reals with $b>1$.
What kinds of algorithms will you use in the comparison? What are their complexities?
For example, when $c \equiv a^b$ or $c \approx a^b$
This question was inspired by the comments on the Mathematics stack exchange question What is the purpose of Stirling's approximation to a factorial?. Especially, those comments left by mjqxxxx, Thomas Andrews and me.
See my answer to this question for some related issues.
In general, computers can only add, subtract, multiply, divide, and bit shift. For the sake of argument, let's assume that you're not calculating $a^b$ in the special case where $a$ is a power of 2 and $b$ is a natural number, because that case reduces to a bit shift, and is therefore easy.
If $b$ is a natural number, and you want to calculate $a^b$, you can use addition-chain exponentiation. Every other case in your question is hard (in general).
Some fast algorithms used to approximate these functions to high accuracy require black magic. To see what I mean by "black magic," take a look at this blog post by Martin Ankerl and an associated paper he links to in Neural Computation. Also see the CORDIC algorithm.
Similar sorts of bit-flipping tricks are explained in Hacker's Delight (the link is to the companion website for the book).
Other ways to calculate good approximations use numerical analysis (see the Wikipedia article on Approximation Theory). One bad way to do it is to rig up an appropriate differential equation and integrate it using a numerical method like Euler's method (like I said, a bad approximation, but you can do it). A better way to do it is to use series approximations. Taylor series converges far too slowly, so something like a Padé approximant or some other type of fast-converging series approximation could be used instead (other rational approximants, Chebyshev series, etc.).
The algorithm you use to approximate the functions above will depend on your architecture, speed requirements, and accuracy requirements.
The problem with talking about complexities is that any algorithm is only going to calculate a floating point approximation of the functions you mention, so the run time is certainly going to depend on the accuracy you demand of your approximation. Even taking that into account, I don't think that computational complexity is a good first approximation of performance; the size of your inputs is going to be measured in bits (i.e., the number of bits it takes to represent $a$, $b$, and $c$), which are going to be precision-dependent, rather than depending on the magnitudes of the numerical inputs themselves. For practical purposes, the precision of the numerical representation of numbers isn't going to vary much (single precision, double precision, quad precision), and you typically don't decide to use that precision based on any computational complexity estimates of scalar functions. The most relevant metric is wall-clock time, and unless you're using a special architecture (embedded systems) or your application really demands a fast exponential (see the blog post link and the Neural Computation link above), the intrinsic libraries in your language of choice are probably just fine.
This is a good question because understanding numerical algorithms and performance is an important prerequisite to being an effective computational scientist. At the same time, it is a poor question because the constraints as posed do not sufficiently qualify it to give a meaningful answer.
The performance of the three computations will strongly depend on the accuracy needed in the final result as well as the minimum precision required to represent the operands. You qualify $a$, $b$, and $c$ as positive real numbers, but we also need to know how many binary digits $d_n$ are required to represent them accurately. To understand the performance considerations for general real numbers, we first need to understand how computers represent integers as well as how it approximates real numbers using floating-point numbers.
When computers operate on an integer $M$, then the number of binary digits needed is obviously equal to the log$_2$ of the magnitude of the integer, plus an extra bit for handling the sign:
$d_n=$log$_2|M|+1$
For example, the number -8 can be represented with 4 binary digits. For performance and space-efficiency, arithmetic logic units (ALUs), responsible for numerical computations of integers on modern processing units, are designed to handle math on integers up to some fixed size, the most common these days being d=32 and d=64. Not just x86 processors like in your computer have ALUs, they are a fundamental building block of computer architecture ubiquitous in today's electronic society. If you are familiar with video game consoles, you might remember the Nintendo 64, a video game system named after the size (in bits), the arithmetic logic units on the console's processor were designed to handle.
Integer additions, subtractions, and multiplications on arithmetic logic units are very efficient, and usually require no more than several cycles to compute. Divisions are less performant, and on modern processors can require as many as several dozen cycles. Performance depends on both the architecture of the processing unit (and corresponding implementation of the arithmetic logic unit) and its frequency. Note that a 64-bit processor can usually perform arithmetic on $x$-bit operands at the same speed for $x$ anywhere between 1 and 64.
In general computing, and especially in scientific computing, integer math is unwieldy for many computations, and another representation of numbers is needed, the so-called 'floating-point' representation. Floating-point numbers represent a compromise between the way modern microprocessors work (carting data around in $n$-bit hunks) and the needs of computation by representing numbers on the processor in truncated scientific notation, using a fixed base $b$ (usually $b=2$ or $b=10$) and representing the number using two integers, a mantissa (significand in some circles) $s$, and an exponent $e$. A given number $x$ is then approximately represented as:
$x = s*b^e$
I say approximately because it should be obvious that even simple rationals such as $\frac{1}{3}$ cannot be represented exactly as a floating-point number for the standard bases. The number of digits committed to the significand determine the accuracy of the number, which is relative to its own magnitude. The IEEE 754 standard specifies a number of rules for how floating-point numbers are expected to behave, including the ranges of the significand and mantissa (and corresponding range and precision) for several important values of $d_n$, so that numerical computations are repeatable within some tolerance. There is quite a bit of subtlety to how floating-point numbers work which I cannot hope to capture in this answer, for a good introduction I recommend "What Every Computer Scientist Should Know About Floating-Point Arithmetic".
A significant amount of intellectual effort over the last 50 years has been invested in improving processor capability to compute arithmetic floating-point operations efficiently. On modern processors, these computations are handled by one or more Floating-point units (FPUs), a more sophisticated version of the arithmetic logic unit designed to perform arithmetic operations on floating-point numbers and usually designed to handle both IEEE 754-specified 32-bit floating-point numbers (often referred to as 'floats') and 64-bit floating-point numbers (often referred to as 'doubles') efficiently. Similar to arithmetic logic units, floating-point units can often compute addition, subtraction, and multiplication in just a few cycles, while division usually requires slightly more.
In most cases, IEEE 754 64-bit floating-point 'doubles' are sufficient for numerical computations, so let us assume that $a$, $b$, and $c$ are each represented as 64-bit doubles, and you are interested in the performance of the three computations as scalar operations on an Intel Nehalem architecture using the x87 floating-point instruction subset, i.e. you are not interested in calculating these operations in a for loop or over a range of data, and you don't want to use the vector extensions. Instruction latency information is collected from Agner Fog's excellent set of instruction reference tables for Intel/AMD architectures.
1 General exponentiation is often implemented with the following identity:
$a^b = \beta^{a\cdot\text{log}_\beta b}$
Where $\beta$ is either $2$ or $e$ (in this case, I use $\beta=2$). Assuming you are willing to throw away some accuracy in the result (the x87 unit does its computations in 80 bits of precision, but this is insufficient for certain ranges of values for $a$ and $b$), this computation can be done with the FYL2X hardware instruction to compute $t=a\cdot\text{log}_2 b$ and the F2XM1 hardware instruction (with some scaling help) to calculate $2^t$. Assuming ~20 cycles for handling the scaling:
FYL2X + F2XM1 + ~20 = 80 + 51 + ~20 = ~151 cycles
2 This can be transformed to two logarithms and a division by the change of basis identity and does not need rescaling for an accurate result.
2*FYL2X + FDIV = 2*80 + (7 to 27) = 167 to 187 cycles
[3] This is equivalent to a division followed by an exponentiation, so [1] plus FDIV, ~175 cycles.
Let me see if I can paraphrase the question:
Answer: it really depends on whether or not c has any dependence on a, and how a compares to b (greater than, less than, or equal).
I will run through some of the cases that you specified about the relationship between $c$, $b$, and $a$:
Assumption 1: Suppose $c$ is a constant, then $\log_a(c) = \ln(c)/\ln(a)$, which does not even approach infinity at all (it approaches zero). In this case, $\log_a(c)$ is an asymptotic lower bound for $a^b$ as $a$ approaches infinity, but it is not a "tight" asymptotic bound. Using the nomenclature and notation popularized by Cormen et al (Introduction to Algorithms, 3rd Edition), $a^b = \omega(\log_a(c))$.
Assumption 2: Suppose $c=a^b$. Then, $\log_a(a^b)=b$. Then, $b$ is constant, while $a^b$ grows without bound as a approaches infinity. Thus, $log_a(c)$ again is an asymptotic lower bound, but not a tight one. So, $a^b = \omega(\log_a(c))$.
Assumption 3: Suppose $c$ is approximately $a^b$. It is unclear in what sense 'approximately' means here, but if we assume that this means $a^b$ is a tight asymptotic bound (that is $c=\Theta(a^b)$, then this produces the same result as in assumption 2.
Again, it depends on the relation between $a$,$b$, and $c$. Though there are more possibilities than I will enumerate here, we can consider the following:
Assumption 1: Suppose $c$ is a constant. Then $c^{1/b}$ is a constant for any given $b$. In this case, $c^{1/b} = o(\log_a(c))$
Assumption 2: Suppose $c = a^b$. Then, $\log_a(c)= a$ and $c^{1/b} = a$. Thus, $\log_a(c) = \Theta(c^{1/b})$
Assumption 3: Suppose $c$ is approximately $a^b$. Again, if we assume this means $a^b$ is an asymptotically tight bound for $c$, then we get the same result as assumption 2.
Assumption 1: Suppose $c$ is a constant. Then $c^{1/b}$ is a constant, while $a^b$ grows without bound as a approaches infinity. Thus, $c^{1/b}=o(a^b)$
Assumption 2: Suppose $c=a^b$. Then $c^{1/b}=a$. Since $b>1$, then $a^b$ must always grow faster than $c^{1/b}$.
There may be a few more cases which I have omitted here, but in the end, it really depends on the assumptions that you make about the relation between the numbers $a$, $b$, and $c$ (and which variable is allowed to approach infinity!)
