Bailey-Borwein-Plouffe-Formel

In der Mathematik bezeichnet die Bailey-Borwein-Plouffe-Formel (BBP-Formel) eine 1995 vom kanadischen Mathematiker Simon Plouffe entdeckte Summenformel zur Berechnung der Kreiszahl $\pi$.

Die von Plouffe entdeckte Reihe für $\pi$ ist:

$\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)$

Die Formel ist nach den Autoren David H. Bailey, Peter Borwein und Simon Plouffe des Zeitschriftenartikels benannt, in dem sie erstmals veröffentlicht wurde. Das Erstaunliche an dieser speziellen Formel ist, dass man daraus mit ein wenig Umstellen einen Algorithmus ableiten kann, der eine beliebige Ziffer der Darstellung von $\pi$ im Hexadezimalsystem ohne Berechnung der vorherigen Ziffern ermittelt (Ziffer-Extraktion).

Polylogarithmische Konstante

Seit Plouffes Entdeckung wurden viele ähnliche Formeln der Gestalt

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

entdeckt, die sich zu anderen fundamentalen mathematischen Konstanten (in der Darstellung zur Basis $b$) aufsummieren, wie z. B. zu den polylogarithmischen Konstanten Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \pi ^{2},\zeta (3)} und zur Catalanschen Konstanten $G$. Man bezeichnet diese Formeln als BBP-Reihen zur Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} . Die Frage, zu welchen mathematischen Konstanten BBP-Reihen existieren, ist bislang unbeantwortet. Zu folgenden Primzahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} existiert für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \log\,p} eine BBP-Reihe:

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 und 59 sind die kleinsten Primzahlen, die in dieser Liste fehlen. Es ist jedoch unbewiesen, ob zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \log 23} tatsächlich keine BBP-Reihe existiert. Vermutlich gibt es für Quadratwurzeln Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {\sqrt {2}},{\sqrt {3}},{\sqrt {5}},\dotsc } , die Eulersche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e} und die Eulersche Konstante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma} keine BBP-Reihe, da das (vermutlich) keine polylogarithmischen Konstanten sind.

BBP-Algorithmus

An einem Beispiel soll gezeigt werden, wie man die Ziffern einer Zahlendarstellung erhält. So bekommt man z. B. die 4. dezimale Nachkommastelle von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pi} durch

Multiplikation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 10^3} …	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 10^3\pi = 3141{,}5926\ldots}
Wegschneiden des ganzzahligen Teils …	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 10^3\pi\,\bmod\, 1 = 0{,}5926\ldots}
Multiplikation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 10} …	Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (10^{3}\pi \,{\bmod {\,}}1)\cdot 10=5{,}926\ldots }
und Wegschneiden des gebrochenen Teils …	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lfloor(10^3\pi\,\bmod\, 1)\cdot 10\rfloor = 5}

wobei zur Notation der Modulo-Operator und die Gauß-Klammer verwendet werden.

Analog ergibt sich die $n$-te Stelle der Hexadezimaldarstellung Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \sum _{k=0}^{\infty }{\frac {z_{k}}{16^{k}}}} von $\pi$ zu

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

Multiplikation der Plouffe-Formel mit $16^{n-1}$ ergibt nach Unterteilung in vier Terme

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\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}}.}

Da im Ausdruck für Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle z_{n}} nur der gebrochene Teil von Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 16^{n-1}\pi } eingeht, kann man bei der Berechnung der $\sigma _{t}$ einen ganzzahligen Teil von den ersten $n$ Summanden entfernen, um die Größe der Zwischenergebnisse zu begrenzen. Das erreicht man durch Anwendung des Operators ${\bmod {(}}8k+t)$ auf den Zähler. Die restlichen Summanden mit $k\geq n$ haben keinen ganzzahligen Teil. Damit erhält man (unter Verwendung des Zeichens $\equiv$ für Kongruenz):

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

Die diskrete Exponentialfunktion im Zähler der ersten Summe kann man mit der binären Exponentiation effizient berechnen, wobei die Zwischenergebnisse kleiner als Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 64n^{2}} bleiben. Damit gilt

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

Da die Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \sigma '_{t}} und ihre Linearkombination noch einen ganzzahligen Teil enthalten können, muss dieser noch entfernt werden. Somit ist

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

Vorteile des BBP-Algorithmus

Diese Methode, nur die gerade benötigte Stelle von $\pi$ zu extrahieren, erspart den Speicherplatz für die vorherigen Stellen. Weiter kann man einfachere Datentypen für die Speicherung der gewonnenen Stellen verwenden, die wiederum auch kürzere Zugriffszeiten haben, was den Algorithmus letztlich schneller macht. Daher hat diese Methode in vielen Anwendungen alle vorherigen Algorithmen zur Berechnung von $\pi$ (die größere und komplexere Datentypen benötigten) überflüssig gemacht.

Bellard-Formel

→ Hauptartikel: Bellard-Formel

Fabrice Bellard entdeckte diese ähnliche Formel 1997. Sie ist etwa 43 % schneller als BBP:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\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)} .

Literatur

• Marc Chamberland: Binary BBP-Formulae for Logarithms and Generalized Gaussian-Mersenne Primes. Journal of Integer Sequences, Vol. 6, 2003, nur digital (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 (Hrsg.): What’s happening in the Mathematical Sciences. Band 6, S. 29–39. AMS 2006.

Weblinks

• David H Bailey Persönliche Webseite
• Eine ausführliche Anleitung mit konkretem Beispiel. (Memento vom 10. April 2014 im Internet Archive).
• Implementierung in Python. (Memento vom 16. November 2015 im Internet Archive).