# What's the fastest known running time for a spigot algorithm for computing an arbitrary digit of $\pi$?

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.

## 1 Answer

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.

• 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. – Timothy Jun 3 '15 at 17:41
• @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. – Meni Rosenfeld Feb 19 '16 at 13:46