1
$\begingroup$

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.

  • 1
    $x=\log c/ \log d$. You should have the $\log$ function available in your program library.2012-04-05
  • 0
    I'm trying to make it more simple than that, if that's okay. Something that can be easily built into processor hardware (only using and, not, add, subt, mult, loop/goto, etc.)2012-04-05
  • 2
    Writing logarithm in terms of and,or,not etc. is really a programming question rather than a math question, I think.2012-04-05
  • 2
    if you can be more specific about the expected the input, it may be possible (for example) to use a look-up table. this is really a programming question.2012-04-05
  • 1
    Is there any more specific information you can give about the values that $c$ and $d$ will take? Or what precision you want on $x$? For example, $c$ and $d$ might be 8-bit numbers between $0$ and $1$. If you know an upper and lower bound, we could make a rational function that approximates $\log$ to whatever degree you desire. Depending on that degree and the upper and lower bounds, this might be faster than using $\log$ directly.2012-04-05
  • 0
    I think there are math answers to this question, if you can provide more detail. Otherwise, this is a programming/hardware question. Some processors come with the $\log$ function built into the circuitry of the hardware. Generally, it will be hard to beat that with any clever math, if it is available to you.2012-04-05
  • 0
    c, d, and x are each 12-bit floating-point numbers (-4096 to 4095 with progressively decreasing fractional precision as the number approaches its upper and lower limit)2012-04-05
  • 0
    if these are floating point numbers then your programming language's log function is likely optimised more than any other suggestion you'll get here.2012-04-08

5 Answers 5

0

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.

  • 0
    Funny, using the built-in log function on the CPU with no parallelism and optimization turned off, I can do 30 *million* operations per second on my machine...2012-04-08
  • 0
    fascinating... which language?2012-04-09
  • 0
    C++: `#include int main (int argc, char **argv) { for (float i = 0; i < 30*1000*1000; i++) float j = std::log(i); }`2012-04-09
  • 0
    I'll keep that in mind, but I was testing mine in Java. Perhaps it'd be faster when I actually write it in Assembler or make hardware to do it.2012-04-10
3

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.

3

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.

3

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.

2

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$.

  • 2
    [An approximation by rational functions](http://en.wikipedia.org/wiki/Pad%C3%A9_approximation) is likely more efficient here than the Taylor approximations (by polynomials).2012-04-05
  • 0
    There are infinitely many values (working with double floats), so a precomputed table won't do.2012-04-07
  • 0
    @Supuhstar It depends on how precise you need the results to be. Double floats have a 52-bit mantissa, which is enough to represent the result to about one part in $10^{16}$. If you only needs the results accurate to one part in 100 (you didn't say) then you don't need a big table. The table size also depends on the size of the input (which you also didn't say) but at least one of those is not a float but an integer.2012-04-07
  • 0
    They each need to be accurate to the 4th decimal place. They are ALL floats.2012-04-08