That is, for the fastest known algorithm for doing so, how many steps will it compute the $n^{\text{th}}$ digit of $\pi$ in? I know some people define running time as the number of steps it will take to compute any digit between the $\exp(n)^{\text{th}}$ digit and the $\exp(n + 1)^{\text{th}}$ digit.


The fastest known algorithms are based on the Bailey-Borwein-Plouffe formula. A particular variation later developed by Plouffe (see here) can be used to calculate the base-$10$ digits of $\pi$ by using the formula $$ \pi + 3 = \sum_{n=1}^{\infty} \frac{n 2^n n!^2}{(2n)!} $$ Plouffe's method calculates the $n^{\text{th}}$ digit of $\pi$ in $\operatorname{O}\left(n^3\log(n)^3\right)$ time. For more details check out the paper.

  • $\begingroup$ According to en.wikipedia.org/wiki/…, all the digits of π can be computed in order in time n (log n)^2 2^(log * n) where log*n is the super-logarithm of n. There's no way the fastest spigot algorithm running time is slower than the fastest algorithm running time for an algorithm that computes all the digits in order. I believe the fastest known spigot algorithm runs faster than time n (log n)^2 2^(log * n) because according to π was only cumputed to 12.1 trillion digits, yet the 2 quadrillionth binary digit was computed. $\endgroup$ – Timothy Jun 3 '15 at 17:41
  • 1
    $\begingroup$ @Timothy: The advantage of Spigot algorithms is space, not time. It's difficult to find straight answers about this, but as I recall the best bit-extraction algorithm has more or less the same complexity as the best algorithm to calculate all digits, but can be used with less memory (I think, logarithmic in digit position, as opposed to linear). Extracting a decimal digit has significantly higher runtime, but also possible with little memory. $\endgroup$ – Meni Rosenfeld Feb 19 '16 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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