Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
$x=\log c/ \log d$. You should have the $\log$ function available in your program library. –  David Mitra Apr 5 '12 at 0:41
    
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.) –  Supuhstar Apr 5 '12 at 0:44
2  
Writing logarithm in terms of and,or,not etc. is really a programming question rather than a math question, I think. –  GEdgar Apr 5 '12 at 0:50
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. –  Ronald Apr 5 '12 at 0:55
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. –  alex.jordan Apr 5 '12 at 2:23

5 Answers 5

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.

share|improve this answer
    
Thank you for this! However, I've gone with a much more efficient approach –  Supuhstar Apr 7 '12 at 3:25

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.

share|improve this answer

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

share|improve this answer
2  
An approximation by rational functions is likely more efficient here than the Taylor approximations (by polynomials). –  alex.jordan Apr 5 '12 at 3:14
    
There are infinitely many values (working with double floats), so a precomputed table won't do. –  Supuhstar Apr 7 '12 at 3:26
    
@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. –  MJD Apr 7 '12 at 18:35
    
They each need to be accurate to the 4th decimal place. They are ALL floats. –  Supuhstar Apr 8 '12 at 7:05

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.

share|improve this answer
up vote 0 down vote accepted

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.

share|improve this answer
    
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... –  Rahul Apr 8 '12 at 7:22
    
fascinating... which language? –  Supuhstar Apr 9 '12 at 22:20
    
C++: #include <cmath> int main (int argc, char **argv) { for (float i = 0; i < 30*1000*1000; i++) float j = std::log(i); } –  Rahul Apr 9 '12 at 22:48
    
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. –  Supuhstar Apr 10 '12 at 2:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.