# 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.

• Oct 19, 2023 at 22:59
• Does the discussion here answer your question? Computing π with the Bailey-Borwein-Plouffe Formula Oct 20, 2023 at 15:52
• @TimothyChow No, it doesn't answer my question at all. They just say that the term gets small quickly as $k$ increases and the code still doesn't say anything. They write "right==rnew" but right actually doesn't equal rnew, this is the whole point of my question! Please delete your comment. Oct 20, 2023 at 16:14

Bounding this sum is not hard, it is majorized by a geometric progression. If you forget about the summands starting from $$n + p$$ (in your terms this means $$s = n + p - 1$$) $$\sum_{k = n + p}^{\infty} \frac{16^{n - k}}{8k + m} < \frac{1}{8n} \sum_{n + p}^{\infty} 16^{n - k} = \frac{1}{8n} \sum_{k = p}^{\infty} 16^{-k} = 16^{-p} \frac{2}{15n}$$ It will quickly become less than your machine precision and will not bother your first digit.
I suppose there theoretically can be an edge case when the first sum is very close to an exact hexadecimal fraction from below which should be handled carefully, and if $$\pi$$ is normal, this will happen eventually, but I don't know if this happens in the reasonable range of $$n$$.
• I agree that the sentence "[...] computationally at least as hard as computing all hexadecimal digits" in my post is misleading/incorrect. For what it's worth: It reflects my initial idea of evaluating $\sum_{k=n+1}^\infty$ in closed form, then bounding the result. Obviously that would not be a good idea. Nov 9, 2023 at 16:33
• You should not compute $s$ and $t$ as written in your post. First compute everything without the last sums that we are discussing now. Then start adding the summands, and stop when the upper bound $4\cdot16^{-p}\frac{2}{15n}$ is less than the distance of your current number to the next number of form $n.a00000\dots$. Then the rest of the summands will not affect the digit you are computing. Nov 9, 2023 at 16:47
• ($4$ should be changed to $8$, the sum of coefficients in the formula for $t$) Nov 9, 2023 at 16:50