# Computing the $n$-th bit of the binary representation of $\pi$

I (only) learned today about the following fact:

The $$n$$-th binary digit of $$\pi$$ is computable without calculating all the previous digits.

This apparently has been discovered in 1995, and follows from the Bailey—Borwein—Plouffe formula: $$\pi = \sum_{n=0}^\infty \frac{1}{16^n}\left(\frac{4}{8n+1}-\frac{2}{8n+4}-\frac{1}{8n+5}-\frac{1}{8n+6}\right)$$ This in turn leads to an $$O(n\log n)$$-time algorithm to compute the $$n$$-th digit of the hexadecimal expansion of $$\pi$$ (and so also of the binary one), interestingly without computing the intermediate ones. (Interestingly too, it's apparently unknown how to do that for the base-10 expansion.)

My question, out of sheer curiosity, is whether anything better is known? Either deterministically or in a randomized fashion, what is the fastest algorithm known for the task "given $$n$$ as input, compute the $$n$$-th digit of the binary expansion of $$\pi$$"? (Also, is there any lower bound?)

Also, is there any interesting application/implication?

• BBP might only be $n\log^3 n$. See the comments here cstheory.stackexchange.com/q/39855/129 Dec 11 '20 at 2:01
• I don't think these answer it, but they're related and might be of interest: cstheory.stackexchange.com/q/31932/129 and cstheory.stackexchange.com/q/21787/129 Dec 11 '20 at 2:03
• See also rjlipton.wordpress.com/2010/07/14/… and cs.nyu.edu/exact/doc/pi-log.pdf. The latter fixes a purported gap in BBP and argues that the $n$th bit can be computed in logspace. Dec 11 '20 at 4:00
• Note that using standard methods that do compute the intermediate digits, you can compute the first $n$ digits of $\pi$ all at once in time $O(M(n)\log n)=O(n(\log )^2)$. In contrast, BBP needs about that time to compute a single digit. Thus, it has a rather abysmal performance timewise. In terms of complexity, the only advantage of the BBP is with respect to space: you can compute the $n$th digit in space $O(\log n)$ (whereas the traditional methods require space $O(n)$). Dec 11 '20 at 7:09
• I should perhaps stress that the existence of a $O(\log n)$-space algorithm does not require the BBP algorithm either, there are other methods. In particular, $\pi$, and other functions and constants expressible by sufficiently nice Taylor series for that matter, can be computed (that is, approximated) in uniform $\mathrm{TC}^0$, and therefore in log-space. (However, the algorithm obtained this way would require a lot of time, albeit still polynomial.) Dec 11 '20 at 7:35