Bailey Borwein Plouffe formula

In mathematics , the Bailey-Borwein-Plouffe formula (BBP formula ) describes a sum formula for calculating the circle number, discovered in 1995 by the Canadian mathematician Simon Plouffe . ${\displaystyle \pi }$

Discovered by Plouffe series for is: ${\displaystyle \pi }$

${\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}{8k+6}}\right)}$

The formula is named after the authors David H. Bailey , Peter Borwein, and Simon Plouffe of the magazine article in which it was first published. The amazing to this particular formula is that one of it with a little changing an algorithm can be derived any one of the digit of the display of the hexadecimal determined without calculating the previous figures (point extraction). ${\displaystyle \pi }$

Polylogarithmic constant

Since Plouffe's discovery, there have been many similar formulas of shape

${\displaystyle \alpha =\sum _{k=0}^{\infty }{\frac {p(k)}{b^{k}q(k)}}}$

discovered that add up to other fundamental mathematical constants (in the representation for the base ), such as B. to the polylogarithmic constants and to the Catalan constants . These formulas are called the base BBP series . The question of which mathematical constants exist for BBP series has not yet been answered. The following prime numbers exist for a BBP series: ${\displaystyle b}$ ${\displaystyle \pi ^{2},\zeta (3)}$ ${\displaystyle G}$ ${\displaystyle b}$ ${\displaystyle p}$ ${\displaystyle \log \,p}$

2, 3, 5, 7, 11, 13, 17, 19, 29, 31, 37, 41, 43, 61, 73, 109, 113, 127, 151, 241, 257, 331, 337, 397, 683, 1321, 1429, 1613, 2113, 2731, 5419, 8191, 14449, 26317, 38737, 43691, 61681, 65537, 87211, 131071, 174763, 246241, 262657, 268501, 279073, 312709, ...

23, 47, 53 and 59 are the smallest prime numbers that are missing from this list. However, it has not been proven whether there is actually no BBP series. Probably there is no BBP series for square roots , Euler's number and Euler's constant , since these are (presumably) not polylogarithmic constants. ${\displaystyle \log 23}$ ${\displaystyle {\sqrt {2}},{\sqrt {3}},{\sqrt {5}},\dotsc }$ ${\displaystyle e}$ ${\displaystyle \gamma }$

BBP algorithm

An example will show how to get the digits of a number representation. So you get z. B. the 4th decimal place of through ${\displaystyle \pi }$

Multiplication by ... ${\displaystyle 10^{3}}$	${\displaystyle 10^{3}\pi =3141{,}5926\ldots }$
Cutting away the integer part ...	${\displaystyle 10^{3}\pi \,{\bmod {\,}}1=0{,}5926\ldots }$
Multiplication by ... ${\displaystyle 10}$	${\displaystyle (10^{3}\pi \,{\bmod {\,}}1)\cdot 10=5{,}926\ldots }$
and cutting away the broken part ...	${\displaystyle \lfloor (10^{3}\pi \,{\bmod {\,}}1)\cdot 10\rfloor =5}$

The modulo operator and the Gaussian brackets are used for the notation .

The -th digit of the hexadecimal representation of zu results analogously ${\displaystyle n}$ ${\displaystyle \sum _{k=0}^{\infty }{\frac {z_{k}}{16^{k}}}}$ ${\displaystyle \pi }$

${\displaystyle z_{n}=\lfloor (16^{n-1}\pi \,{\bmod {\,}}1)\cdot 16\rfloor .}$

Multiplication of the Plouffe formula by gives after subdividing into four terms ${\displaystyle 16^{n-1}}$

${\displaystyle 16^{n-1}\pi =4\sigma _{1}-2\sigma _{4}-\sigma _{5}-\sigma _{6}\quad {\text{ mit }}\quad \sigma _{t}=\sum _{k=0}^{\infty }{\frac {16^{n-k-1}}{8k+t}}.}$

Since only the fractional part of is included in the expression for , one can remove an integer part from the first summands when calculating in order to limit the size of the intermediate results. This is achieved by applying the operator to the counter. The remaining summands with do not have an integral part. This gives (using the symbol for congruence ): ${\displaystyle z_{n}}$ ${\displaystyle 16^{n-1}\pi }$ ${\displaystyle \sigma _{t}}$ ${\displaystyle n}$ ${\displaystyle {\bmod {(}}8k+t)}$ ${\displaystyle k\geq n}$ ${\displaystyle \equiv }$

${\displaystyle \sigma _{t}\;\equiv \;\sigma '_{t}=\sum _{k=0}^{n-1}{\frac {16^{n-k-1}{\bmod {(}}8k+t)}{8k+t}}+\sum _{k=n}^{\infty }{\frac {16^{n-k-1}}{8k+t}}{\pmod {1}}}$.

The discrete exponential function in the numerator of the first sum can be calculated efficiently using binary exponentiation , with the intermediate results remaining smaller than . This applies ${\displaystyle 64n^{2}}$

${\displaystyle 16^{n-1}\pi \equiv 4\sigma '_{1}-2\sigma '_{4}-\sigma '_{5}-\sigma '_{6}{\pmod {1}}}$.

Since the and its linear combination can still contain an integer part, this must still be removed. So is ${\displaystyle \sigma '_{t}}$

${\displaystyle z_{n}=\lfloor ((4\sigma '_{1}-2\sigma '_{4}-\sigma '_{5}-\sigma '_{6})\,{\bmod {\,}}1)\cdot 16\rfloor .}$

Advantages of the BBP algorithm

This method of extracting only the currently required position from saves the storage space for the previous positions. Furthermore, one can use simpler data types for the storage of the obtained positions, which in turn also have shorter access times, which ultimately makes the algorithm faster. Therefore, in many applications, this method has made all previous algorithms for computing (which required larger and more complex data types) obsolete. ${\displaystyle \pi }$ ${\displaystyle \pi }$

Bellard formula

→ Main article : Bellard formula

Fabrice Bellard discovered this similar formula in 1997. It's about 43% faster than BBP:

${\displaystyle \pi =\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{2^{10k+6}}}\,\left({\frac {2^{8}}{10k+1}}-{\frac {2^{6}}{10k+3}}-{\frac {2^{5}}{4k+1}}-{\frac {2^{2}}{10k+5}}-{\frac {2^{2}}{10k+7}}+{\frac {1}{10k+9}}-{\frac {1}{4k+3}}\right)}$.

literature

• Marc Chamberland: Binary BBP-Formulas for Logarithms and Generalized Gaussian-Mersenne Primes. Journal of Integer Sequences, Vol. 6, 2003, digital only (PDF; 175 kB).
• David H. Bailey: A Compendium of BBP-Type Formulas for Mathematical Constants. 2004, online (PDF; 215 kB).
• Barry Cipra: Digits of Pi. In: D. Mackenzie, B. Cipra (Eds.): What's happening in the Mathematical Sciences. Volume 6, pp. 29-39. AMS 2006.

Individual evidence

1. ↑ David H. Bailey , Peter B. Borwein , Simon Plouffe : On the Rapid Computation of Various Polylogarithmic Constants . In: Mathematics of Computation . 66, No. 218, April 1997, pp. 903-913. doi : 10.1090 / S0025-5718-97-00856-9 .
2. ↑ Follow A104885 in OEIS

Web links

• David H. Bailey's homepage
• Detailed instructions with a concrete example. ( Memento of April 10, 2014 in the Internet Archive ).
• Implementation in Python. ( Memento from November 16, 2015 in the Internet Archive ).