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

Question

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.

Answer 1

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.