Skip to main content
1 of 6
Nomas2
  • 317
  • 1
  • 10

Implementing the $\pi$ BBP algorithm

The formula $$\pi = \sum_{k=0}^\infty \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6}\right)$$ is a basis of the BBP algorithm for calculating arbitrary hexadecimal digits of $\pi$ without needing to calculate the preceding digits.

Now I tried to actually implement that algorithm:

  1. Define $$s(m,n,r)=\sum_{k=0}^n \frac{16^{n-k}\operatorname{mod}\,(8k+m)}{8k+m}+\sum_{k=n+1}^r \frac{16^{n-k}}{8k+m}.$$
  2. Define $$t(n,r)=4s(1,n,r)-2s(4,n,r)-s(5,n,r)-s(6,n,r).$$
  3. Define $$u(n,r)=\lfloor 16(t(n,r)-\lfloor t(n,r)\rfloor)\rfloor .$$

Then, for appropriate $r$, $u(n,r)$ gives the $(n+1)$th hexadecimal digit of $\pi$: $$\pi=3.243\mathrm{F}6\mathrm{A}8885\mathrm{A}308\mathrm{D}\ldots_{16}.$$

Question

For a given $n$, what is the minimal appropriate $r$?

What I tried

For what it's worth, I noticed that choosing $r=0$ still correctly gives the first $20$ (and maybe even more) hexadecimal digits of $\pi$! I think it should somehow be possible to bound the annoying term $$\sum_{k=n+1}^r \frac{16^{n-k}}{8k+m}.$$ For example, for $n=0$ and $m=1$ I obtained $$\frac{1}{16}\log\frac{16}{15}\lt \sum_{k=1}^\infty \frac{1}{16^k (8k+1)}\lt \frac{1}{8}\log\frac{16}{15}$$ (because $\sum_{k=1}^\infty \frac{1}{16^k 8k}$ and $\sum_{k=1}^\infty \frac{1}{16^k (8k+8k)}$ have a nice closed form; this should be possible for further combinations of $n$ and $m$ but I don't know how to put it all together.)

This question has also been asked on Math StackExchange (https://math.stackexchange.com/questions/4789996/implementing-the-pi-bbp-algorithm) but no one has answered.

Nomas2
  • 317
  • 1
  • 10