Bailey-Borwein-Plouffe formula

The Bailey-Borwein-Plouffe formula (or BBP formula) allows us to calculate the nth digit of π in base 2 (or 16) without having to find the precedents, quickly and using very little memory space on the computer. Simon Plouffe along with David Bailey and Peter Borwein found this formula on September 19, 1995 using a computer program called PSLQ that looks for relationships between integers.

The BBP formula

${displaystyle pi =sum _{k=0}^{infty }{frac {1}{16^{k}}}}{left({frac {4}{8k+1}}}}{frac {2}{8k+4}}}}}{frac {1}{8k+5}}}}-{frac {1{1}{8k}{1}{1}{8k$

The proof of this formula is below.

Using the formula to calculate the decimal places of the number π

The following is the calculation of the nth hexadecimal digit of π.

First note that the digit at position N+1 of π in base 16 is the same as the first hexadecimal digit of 16^Nπ. Indeed, as in base 10, multiplying a number in base 16 by 16 is equivalent to moving the decimal point one place to the right. Thus, multiplying by 16^N moves the comma N places to the right. The original problem reduces to computing the first digit of 16^Nπ. Using the BBP formula:

${displaystyle 16^{N}pi =sum _{k=0}{^{infty 16}{N-kleft({frac {4}{8k+1}}}}-{frac {2}{8k+4}}-{frac {1}{8k+5}}}-{frac {1}{8k+6}}}}}}}}}}$

Calculating the first hexadecimal digits to the right of the comma of this number is not easy for two reasons: the number is very large, and the sum is infinite.

Suppose ${displaystyle S_{N}(a)=sum _{k=0}^{infty }{frac {16^{N-k}{8k+a}}}}}}}}}}$. The calculation of the first hexadecimal digits of S_N(a) to obtain 16^Nπ, through the relationship:

${displaystyle 16^{N}pi =4 S_{N}(1)-2S_{N}(4)-S_{N}(5)-S_{N}(6)}}$

Decompose the sum S_N(a) into two:

${displaystyle S_{N}(a)=sum _{k=0}{infty }{frac {16^{N-k}{8k+a}=sum _{k=}{N-1}{frac}{16^{N-k}}{8k+a}}{8k+a}{$

A_N(a) and B_N(a) can be computed independently.

BN(a) calculation

${displaystyle B_{N}(a)=sum _{k=N}^{infty }{frac {16^{N-k}}{8k+a}}}}}}}}}}$

Although this is an infinite sum, it is very easy to calculate, because its terms are small and rapidly decreasing.

• The first term of the sum is: ${displaystyle b_{N}={frac {1}{8N+a}}}}$. If the enesimo hexadecimal digito of π is sought (N = 1 000 000 000 for example), the first term is much lower than 1.
• In addition, each term has a zero more to the right of the coma than the previous one, because for k ≥ N, b_k ▪ 16 b_k+1:

${displaystyle {frac {b_{k}}{b_{k+1}}}}={frac {16^{N-k}}{16^{N-(k+1)}}}{frac {8(k+1)+a}{8k+a}}}{6left(1+{frac {8}{8k+a}{right}{8k+a}{right}{right)}{8k+a}}{right$.

Finally, the sum B_N(a) is of the form (in the worst case):

${displaystyle B_{N} = *********$

${displaystyle +$