2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ crosspost math.stackexchange.com/questions/4789996/… $\endgroup$
    – Will Jagy
    Oct 19, 2023 at 22:59
  • $\begingroup$ Does the discussion here answer your question? Computing π with the Bailey-Borwein-Plouffe Formula $\endgroup$ Oct 20, 2023 at 15:52
  • $\begingroup$ @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. $\endgroup$
    – Nomas2
    Oct 20, 2023 at 16:14

1 Answer 1

1
+100
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Well, the problem is that the majorization by geometric series may not be "enough": you see, the algorithm uses floor functions which have discontinuities, so even a small error can cause big problems. The majorization by the geomtric series could be useful if only the floor functions can be somehow thrown away. Maybe the problem can be solved but I don't see how. $\endgroup$
    – Nomas2
    Nov 9, 2023 at 16:23
  • $\begingroup$ 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. $\endgroup$
    – Nomas2
    Nov 9, 2023 at 16:33
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 9, 2023 at 16:47
  • 1
    $\begingroup$ ($4$ should be changed to $8$, the sum of coefficients in the formula for $t$) $\endgroup$ Nov 9, 2023 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.