Calculating x^y, 2^x, etc.
Code:
Theory:
x^y
If y is an integer, we can repeatedly multiply (or use even faster algorithms that repeatedly square and multiply).
If y is not an integer, we generally make the substitution
x^y = e^(y ln( x )) or x^y = 2^(y log2( x ))
and use some subroutine to calculate ln(x) and e^b -- or, alternatively, calculate log2(x) and 2^b.
(Is there a page somewhere on massmind describing logarithms and exponentials? Move the following text there.)
"Richard Feynman and The Connection Machine" by W. Daniel Hillis 1989 briefly describes Richard Feyman and the algorithm:
An Algorithm For Logarithms
Feynman worked out ... the subroutine for computing logarithms. I mention it here not only because it is a clever algorithm, but also because it is a specific contribution Richard made to the mainstream of computer science. He invented it at Los Alamos.
Consider the problem of finding the logarithm of a fractional number between 1.0 and 2.0 (the algorithm can be generalized without too much difficulty). Feynman observed that any such number can be uniquely represented as a product of numbers of the form 1 + 2-k, where k is an integer. Testing each of these factors in a binary number representation is simply a matter of a shift and a subtraction. Once the factors are determined, the logarithm can be computed by adding together the precomputed logarithms of the factors. The algorithm fit especially well on the Connection Machine.... The entire computation took less time than division.
Scott Dattalo has written a far more detailed explanation of Feynman's log2(x) algorithm, with worked-out examples .
Questions: