Skip to main content
5 of 6
added 148 characters in body
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$?

For what it's worth, I noticed that choosing $r=0$ still correctly gives the first $88$ (and maybe even more) hexadecimal digits of $\pi$! Is this just a coincidence?

Bounding $$\sum_{k=n+1}^\infty \frac{16^{n-k}}{8k+m}$$ is maybe computationally at least as hard as computing all hexadecimal digits of $\pi$ to a given place, which would go against the purpose of the whole BBP algorithm.

The power of the BBP probably lies in the fact that we can ignore $\sum_{k=n+1}^\infty \frac{16^{n-k}}{8k+m}$, but I don't know how to prove it.

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