TAOCP 4.3.1 Exercise 39
Let S=\sum_{k\ge0}\frac1{16^k}\left(\frac4{8k+1}-\frac2{8k+4}-\frac1{8k+5}-\frac1{8k+6}\right).
Section 4.3.1: The Classical Algorithms
Exercise 39. [**] [25] (D. Bailey, P. Borwein, and S. Plouffe, 1996.) Explain how to compute the $n$th bit of the binary representation of $\pi$ without knowing the previous $n - 1$ bits, by using the identity
$$\pi = \sum_{k \ge 0} \frac{1}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)$$
and doing $O(n \log n)$ arithmetic operations on $O(\log n)$-bit integers. (Assume that the binary digits of $\pi$ do not have surprisingly long stretches of consecutive 0s or 1s.)
Verified: yes
Solve time: 4m58s
Let
$$ S=\sum_{k\ge0}\frac1{16^k}\left(\frac4{8k+1}-\frac2{8k+4}-\frac1{8k+5}-\frac1{8k+6}\right). $$
Since $\pi=S$, the $n$th binary digit of $\pi$ is determined by the fractional part of $2^nS$. Write
$$ {2^nS} = \left{ \sum_{k=0}^{\lfloor n/4\rfloor} 2^{,n-4k} \left(\frac4{8k+1}-\frac2{8k+4}-\frac1{8k+5}-\frac1{8k+6}\right) + R \right}, $$
where $R$ is the tail with $k>\lfloor n/4\rfloor$. For the finite sum, each term has the form $2^{n-4k}a/m$ with $m=8k+r$. Only its fractional part is relevant, and
$$ \left{\frac{2^{n-4k}a}{m}\right} = \frac{a(2^{n-4k}\bmod m)}{m}\pmod 1. $$
The residue $2^{n-4k}\bmod m$ is obtained by binary exponentiation in $O(\log n)$ arithmetic operations on integers of size $m=O(n)$, hence on $O(\log n)$ bits. There are $O(n)$ values of $k$, so the entire finite sum requires $O(n\log n)$ arithmetic operations.
For the tail,
$$ |R| < \sum_{k>\lfloor n/4\rfloor}\frac{6}{16^k} = O(2^{-n}), $$
so only $O(1)$ additional terms are needed to determine ${2^n\pi}$ to accuracy better than $2^{-c}$ for a fixed constant $c$. Under the stated assumption that the binary expansion of $\pi$ contains no unusually long runs of consecutive $0$s or $1$s, such a fixed accuracy suffices to decide the desired bit from the value of ${2^n\pi}$. Thus the $n$th binary digit of $\pi$ can be computed directly, without computing the preceding digits, using $O(n\log n)$ arithmetic operations on integers having only $O(\log n)$ bits. Hence the BBP formula yields a digit-extraction algorithm for $\pi$. ∎