13
$\begingroup$

I know what the Bailey-Borweim-Plouffe Formula (BBP Formula) is—it's $\pi = \sum_{k = 0}^{\infty}\left[ \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6} \right) \right]$— but how exactly do I use it to calculate a given digit of pi?

$\endgroup$
4
  • 2
    $\begingroup$ It is still work; read the original BBP papers and later follow-ups. en.wikipedia.org/wiki/… "Though the BBP formula can directly calculate the value of any given digit of π with less computational effort than formulas that must calculate all intervening digits, BBP remains linearithmic whereby successively larger values of n require increasingly more time to calculate; that is, the "further out" a digit is, the longer it takes BBP to calculate it, just like the standard π-computing algorithms." $\endgroup$
    – Will Jagy
    Commented Jul 28, 2014 at 20:33
  • 1
    $\begingroup$ @WillJagy I get that the "farther out" a digit is the more time it takes to calculate it. However, that doesn't really relate to my question. My understanding is that the BBP formula is a digit extraction formula—a formula that can be used to calculate a specific digit of pi without needing to calculate the previous digits. My question is—how exactly do I do that? I don't see how the BBP formula can calculate, say, the 23rd digit of pi. $\endgroup$
    – Anonymus
    Commented Jul 29, 2014 at 17:50
  • $\begingroup$ I don't know either. Documentation is plentiful. $\endgroup$
    – Will Jagy
    Commented Jul 29, 2014 at 18:03
  • 1
    $\begingroup$ @Anonymus If you read French, it's explained in details here plouffe.fr/simon/articles/Obsession_de_Pi.pdf $\endgroup$ Commented Oct 13, 2014 at 4:28

2 Answers 2

7
$\begingroup$

The basic idea depends on the following easy result:

The $d+n$-th digit of a real number $\alpha$ is obtained by computing the $n$-th digit of the fractional part of $b^d \alpha$, in base $b$ . (fractional part denoted by $\lbrace \rbrace$.)

For instance: if you want to find the $13$-th digit of $\pi$ in base $2$, you must calculate the fractional part of $2^{12} \pi$ in base $2$.

$\lbrace2^{12} \pi\rbrace=0.\color{red} 1\color{blue} {111011}..._2$

hence $13$-th digit of $\pi $ is $\color{red} 1$.

$\pi=11.001001000011\color{red} 1\color{blue} {111011010101}..._2$

Now if we want to compute the $n+1$-th hexadecimal digit of $\pi$

we only need to calculate $\lbrace 16^{n} \pi\rbrace$

you can do this by using $BBP$ 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) $$

$$16^{n} \pi= \sum_{k = 0}^{\infty} \left( \frac{4 \cdot 16^{n-k}}{8k + 1} - \frac{2\cdot 16^{n-k}}{8k + 4} - \frac{ 16^{n-k}}{8k + 5} - \frac{16^{n-k}}{8k + 6} \right)$$

and

$$\lbrace 16^{n} \pi\rbrace=\bigg\lbrace\sum_{k = 0}^{\infty} \left( \frac{4 \cdot 16^{n-k}}{8k + 1} - \frac{2\cdot 16^{n-k}}{8k + 4} - \frac{ 16^{n-k}}{8k + 5} - \frac{16^{n-k}}{8k + 6} \right)\bigg \rbrace$$

Now let $S_j=\sum_{k=0}^{\infty} \frac{1}{16^k(8k+1)}$ then

$$\color{blue}{\lbrace 16^{n} \pi\rbrace=\lbrace 4\lbrace 16^{n} S_1\rbrace-2\lbrace 16^{n} S_4\rbrace-\lbrace 16^{n} S_5\rbrace-\lbrace 16^{n} S_6\rbrace \rbrace}$$

using the $S_j$ notation

$$\lbrace 16^{n} S_j\rbrace=\bigg \lbrace \bigg \lbrace\sum_{k=0}^{n}\frac{16^{n-k}}{8k+j} \bigg \rbrace+\sum_{k=n+1}^{\infty}\frac{16^{n-k}}{8k+j}\bigg \rbrace $$

$$=\bigg \lbrace \bigg \lbrace\sum_{k=0}^{n}\frac{16^{n-k} \mod {8k+j} }{8k+j} \bigg \rbrace+\sum_{k=n+1}^{\infty}\frac{16^{n-k}}{8k+j}\bigg \rbrace$$

Now compute $\lbrace 16^{n} S_j\rbrace$ for $j=1,4,5,6$, combine these four result, then discarding integer parts.

The resulting fraction, when expressed in hexadecimal notation, gives the hex digit of $\pi$ in position $n+1$ .

$\endgroup$
2
  • 3
    $\begingroup$ What do you mean by "combine these four results" ? $\endgroup$
    – Anthony
    Commented Feb 9, 2017 at 20:34
  • $\begingroup$ I don’t understand. In your case, we still need to sum the first $n$ items. The complexity is still $O(n)$, but the constant is reduced? $\endgroup$
    – Aster
    Commented Dec 21, 2023 at 13:35
-1
$\begingroup$

If you want to calculate the $k$th hex digit, substitute your value for $k$ for everything in the parentheses.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .