How can I find $c=d^x$ using only basic computer functions?

Question

Since this seems more like a math question than programming, I'm placing it here instead of on SO

I'm trying to find $x$ when $c$ and $d$ are known constants (user input and iteration counter, respectively) in the equation $c=d^x$ in a program I'm making. How can I find this without using complex methods? (this operation must be done several thousand times per second, at least)

Please use pseudocode for any examples.

Answer 1

Log is a special function that has the property that if $c=d^x$ then $\log c=x\log d$ and thus $x=\frac{\log c}{\log d}$. To find x in pseudocode, we simply have:

float c, d, x
//assign input for c and d h
x = math.log (c)/math.log(d)  //assigns x the correct value

The log function should be in all math libraries of big programming languages. Java has the log function in the Math class, C++ has it in the math.h library, Python has it in its math library, etc.

If you cannot find this function in a library (which is very unlikely), there are plenty of algorithmic to estimate log. You probably do not need to use any of the numerical analysis methods for finding log as many people suggested, however. Also, the standard log function from a math library should be sufficiently fast.

Answer 2

As the comments suggested, the direct approach is to apply log function.

If you don't want to use log function, I suggest that you write your equation as:

$f(x) = d^x - c$ where c,d are constants.

and you could apply a method of successive approximations to find the root. One such method is this: Wiki-Bisection Method (while it is not the best method, it is the only way that does not involve using log function as far as I know). The link provides an algorithm.

Answer 3

Others have observed that the function you want is $x = {\log c\over \log d}$. So it's enough to be able to quickly calculate logs. Precompute the values of $\log t$ and store them in a table. Then use table lookup. You will not get it to run any faster and you will not find a simpler implementation.

If the table takes too much space for the accuracy you need, store a smaller table, and use table lookup followed by linear interpolation. Linear interpolation goes like this: Suppose you want $\log x$ but your table only has $\log a$ where $a$ is not too different from $x$. If you know that the slope of the log function near $\log a$ is close to $m$, then $\log x\approx \log a + m\cdot(x-a)$, which is quick: you can get $\log a$ from the table and then once you have $m$ you need one multiplication and two additions. For your particular function, $m = 1/a$, so you have $\log x\approx \log a + {x-a\over a}$.

Similarly if you want to trade off more computation for a smaller table you can use second- or third-order interpolation: $\log x\approx \log a + {x - a \over a} - {1\over 2}{(x-a)^2\over a^2}$ or $\log x\approx \log a + {x - a \over a} - {1\over 2}{(x-a)^2\over a^2} + {1\over 3}{(x-a)^3\over a^3} $. To save operations, you'll want to calculate $z = {x-a\over a}$ and then use Horner's method to calculate the polynomial functions of $z$.

Answer 4

Since you need very high performance (and from that we can infer that you need interactive rates), you could perhaps benefit from modern GPUs by employing them for general purpose computing. Their parallelized SIMD nature might be able to severely flunk the time necessary to perform the operations and GPUs love chewing floating point operations. You don't even have to cheat with standard shaders or use clever math tricks to approximate, you can turn to the well established approaches like DirectCompute, OpenCL, CUDA.

If you don't wish to entangle yourself in such complexity for performance, your best bet would be to compare performance between Mark Dominus' table lookup/interpolation approach, alex.jordan's suggestion to use approximation by rational functions and simply brute forcing the log() function in a heavy usage scenario and then choose what suits your needs best. Besides that, there isn't much you can do to squeeze performance/precision. It's either the workload of coding for the GPUs or deciding between computation and memory. Trade-offs, like everything in life.

Answer 5

After looking over all these answers, I've taken them into consideration and come up with the solution: send a modified version of the algorithm from Wikipedia's Binary Logarithm page to the GPU. This takes, on average, 3000ns to calculate, allowing for about 333 $1\over3$ thousand operations per second.