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 die Formel 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^kq(k)}$

entdeckt, die sich zu anderen fundamentalen mathematischen Konstanten (in der Darstellung zur Basis $b$) aufsummieren, wie z. B. zu den polylogarithmischen Konstanten $\pi^2, \zeta(3)$ und zur Catalanschen Konstante G. Man bezeichnet diese Formeln als BBP-Reihen zur Basis b. Die Frage, zu welchen mathematischen Konstanten BBP-Reihen existieren, ist bislang unbeantwortet. Zu folgenden Primzahlen p existiert für $\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 $\log 23$ tatsächlich keine BBP-Reihe existiert. Vermutlich gibt es für Quadratwurzeln $\sqrt2, \sqrt3, \sqrt5, ...$, die Eulersche Zahl e und die Eulersche Konstante $\gamma$ keine BBP-Reihe, da dies (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. Dezimalstelle von $\pi$ durch

Multiplikation mit $10^3$ …	$10^3\pi = 3141{,}5926\ldots$
Wegschneiden des ganzzahligen Teils …	$10^3\pi\,\bmod\, 1 = 0{,}5926\ldots$
Multiplikation mit $10$ …	$(10^3\pi\,\bmod\, 1)\cdot 10 = 5{,}926\ldots$
und Wegschneiden des gebrochenen Teils …	$\lfloor(10^3\pi\,\bmod\, 1)\cdot 10\rfloor = 5$

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

Analog ergibt sich die $n$-te Stelle der Hexadezimaldarstellung $\pi = \sum_{k = 0}^{\infty} \frac {z_k}{16^k}$ von $\pi$ zu

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

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

$16^{n-1}\pi=4\sigma_1-2\sigma_4-\sigma_5-\sigma_6 \quad \mbox{ mit } \quad \sigma_l=\sum_{k=0}^{\infty}\frac{16^{n-k-1}}{8k+l}.$

Da im Ausdruck für $z_n$ nur der gebrochene Teil von $16^{n-1}\pi$ eingeht, entfernen wir zunächst von jedem einzelnen Summanden den ganzzahligen Teil. In den ersten $n$ Summanden von $\sigma_l$ erreichen wir dies durch Anwendung des Operators $\bmod(8k+l)$ auf den Zähler, die restlichen Summanden mit $k\geq n$ haben keinen ganzzahligen Teil. Damit ändert sich $\sigma_l$ ab zu

$\sigma'_l= \sum_{k=0}^{n-1}\frac{(16^{n-k-1}\bmod(8k+l))}{8k+l} + \sum_{k=n}^{\infty} \frac{16^{n-k-1}}{8k+l}$

und es gilt

$16^n\pi\equiv 4\sigma'_1-2\sigma'_4-\sigma'_5-\sigma'_6 \pmod{1}$

unter Verwendung des Zeichens $\equiv$ für Kongruenz. Da die veränderten Summen selbst und erst recht ihre Linearkombination noch ganze Zahlen enthalten können, müssen diese noch entfernt werden. Dann kann man mit $16$ multiplizieren und den gebrochenen Teil wegschneiden, um schließlich $z_n$ zu erhalten.

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 alle vorherigen Algorithmen zur Berechnung von $\pi$ (die größere und komplexere Datentypen benötigten) überflüssig gemacht.

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 (eds). What's happening in the Mathematical Sciences Vol.6, pp29-39. AMS 2006.

Weblinks

• David H. Baileys Homepage
• Eine ausführliche Anleitung mit konkretem Beispiel
• Implementierung in Python