What is the asymptotically fastest known exponentation algorithm?

Question

What is the fastest known algorithm for computing an exponential in binary? It seems that the most straightforward one computes exponentiation in cubic time. I'm wondering what the asymptotically fastest know one is. It is good enough for me to find the fastest one you can find in terms of any multiplication algorithm. Then if a faster multiplication algorithm is found, I will know that that also means there is a faster exponentiation algorithm. I know there are faster multiplication algorithms like Fürer's algorithm.

Answer 1

I don't know about other bases but I know how given any multiplication algorithm, I can compute in terms of any real number all the digits of its exponential to the base $e$ in the time of the multiplication algorithm times the number of digits calculated so far divided by the log of the number of digits calculated so far.

We know that for any real number $x$, $e^x = \frac{1}{0!} + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}...$. Note that for each positive integer $t$, the $x^t$ term of $e^x$ is equal to the $x^{t - 1}$ term times $\frac{x}{t}$. Now suppose you want to calculate it to the accuracy of $n$ digits after the decimal place for some very large number $n$. First, we recognize that for each positive integer $t$, the $x^t$ term is equal to the $x^{t - 1}$ term times $\frac{x}{t}$.

Now, we can start from 0 then add the 1 term. Next, we multiply that term by $\frac{x}{1}$ to the accurace of about $n$ digits then add it to the accuracy of about $n$ digits, next we multiply this term by $\frac{x}{2}$ to the accuracy of about $n$ digits and add it to the accuracy of about $n$ digits. Next we multiply this term by $\frac{x}{3}$ to the accuracy of about $n$ digits and add it to the accuracy of about $n$ digits. Once you get to the term somewhere around $x^{\frac{n}{\log{n}}}$, the term is about the size of $2^{-n}$ so we can stop. Now how many times are you multiplying to get the next term? About $\frac{n}{\log{n}}$.

But wait, how to you compute which number it is you want to multiply be to get the $x^t$ term? That is, how to you calculate $\frac{x}{t}$? By using division, not multiplication. I don't know that it's the case that for any multiplication algorithm, there is a division algorithm that is asymptotically the same speed. However, I know that $t$ is a whole number with at most about $\log{n}$ digits. So division by $t$ up to the accuracy of about $n$ digits can be done in about $n\log{n}$ steps. Each step of getting the next $x^t$ can be done in the time of which ever is more of the multiplication algorithm or division by $t$.

According to the Wikipedia article Fürer's algorithm, it has been conjectured that the asymptotically fastest multiplication algorithm runs in time $O(n \log{n})$. That would mean exponentation to the base $e$ can be done in time $O(n^2)$.

I know that exponentation to another base like 2 can be done by first dividing by $\ln{2}$ then exponentiating to the base $e$. However, there are 2 reasons I'm not sure it can be done as fast as exponentiating to the base $e$. One is we don't know that computing the inverse, the $\ln$ can be done asymptotically as fast as computing the exponential to the base $e$. The other reason is we have to perform a division.

Update:

When I Google searched "fast pi computing algorithm," I found the Wikipedia article Chudnovsky algorithm. According to that article, $\pi$ can be computed in time $O(n\log{(n)}^3)$. I'm wondering if given access to all the binary digit of a number, computing the exponential of it in binary can also be done in time $O(n\log{(n)}^3)$.