-2

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.

Bernard
  • 175,478
Timothy
  • 793

1 Answers1

0

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

Timothy
  • 793
  • If you start at the back end -- $y\leftarrow 1$; $m\leftarrow m_0$; while ($m>0$) { $y\leftarrow \frac1m(x\cdot y)+1$; $m\leftarrow ,m-1$ } -- you can even get away with using much less precision in all but the latest (i.e., small $m$) steps. Not sure if this optimization is enough to lower the $O(n^2)$. (This also assumes that the number representation makes adding $1$ to a float is a relatively trivial task) – Hagen von Eitzen Aug 28 '20 at 20:49
  • @HagenvonEitzen We don't even have one in time $O(n^2)$. I said that was assuming the conjecture that the asymptotically fastest multiplication algorithm is in time $O(n\log{n})$. I didn't read it carefully this time and was also remembering from years ago. It actually said the lower bound was $O(n\log{n})$. Also, I cannot follow your idea without studying it really hard and I don't want to study it really hard. – Timothy Aug 29 '20 at 00:37
  • @HagenvonEitzen I updated the answer. You should read the introduction of the Wikipedia article https://en.wikipedia.org/wiki/Chudnovsky_algorithm. I see that it computes a sum of terms up to the desired number of digits. I don't see how that can be done in time $O(n\log{(n)})^3$. You're just adding a bunch of terms each of which has a factorial. I know the factorial can be easily computed given what the factorial of the number 6 before is by multiplying it by a bunch of small numbers which can be done in time $n\log{n}$. How many times do you have to make that calculation? That doesn't mean – Timothy Sep 07 '20 at 23:49
  • nobody found a legitimate proof of a way to compute $\pi$ that quickly. I might ask a question about that explaining how if they think the reason others think so is too advanced, they will explain that that's what they think. – Timothy Sep 07 '20 at 23:51