What's the fastest algorithm to perform exponentiation?

Question

What's the fastest algorithm to perform exponentiation? Let's assume natural number bases and exponents for simplicity's sake.

What would an efficient math library use?

(When I search for it, I just get results pertaining to algorithms that run in exponential time.)

Answer 1

The problem with all of the binary methods above is that they are limited to integers only. If by "exponentiation" you mean compute the e^x function, the best I have seen is power series that converge quickly, and polynomial, rational, or Pade approximations that are valid over a limited range.

One thing for sure: if you find a lightning fast algorithm for e^x to 96 decimal places, you will also have found a faster way to compute logs (by Newton-Raphson). In fact, Newton-Raphson converges quadratically, so you double the number of digits of precision in your log with each iteration. This was a favorite of Nate Grossman of UCLA back in the Forth days.

Back in the days of four-banger calculators, I used to use e^x = (1+x/1024)^10. Of course that breaks down for x very large or very small, but you can see why it works. If you have a square root button, you can reverse this idea to get logarithms. But you don't need square root for the exponential function.

I wonder if there is some inversion of the AGM algorithm that could do the exponential function... Hmmm....