Bailey-Borwein-Plouffe-Formel

Kernidee der BBP-Formel

Die Bailey-Borwein-Plouffe-Formel (BBP-Formel) ist eine 1995 von Simon Plouffe entdeckte Summenformel zur Berechnung der Kreiszahl π. Sie lautet:

π = ∑_{k=0}^{∞} (1/16ᵏ) · (4/(8k+1) − 2/(8k+4) − 1/(8k+5) − 1/(8k+6)).

Benannt ist sie nach David H. Bailey, Peter Borwein und Simon Plouffe, den Autoren des Zeitschriftenartikels, in dem die Formel erstmals veröffentlicht wurde. Ihre besondere Bedeutung liegt darin, dass sich aus ihr ein Algorithmus ableiten lässt, der eine beliebige Ziffer der Hexadezimaldarstellung von π berechnet, ohne die vorherigen Ziffern bestimmen zu müssen. Dieses Verfahren heißt Ziffer-Extraktion.

Berechnung einzelner Hexadezimalziffern

Das Grundprinzip der Ziffer-Extraktion lässt sich an Dezimalzahlen zeigen. Die 4. Nachkommastelle von π erhält man durch Multiplikation mit 10³, Entfernen des ganzzahligen Teils, erneute Multiplikation mit 10 und Entfernen des gebrochenen Teils:

10³π = 3141,5926…

10³π mod 1 = 0,5926…

(10³π mod 1) · 10 = 5,926…

⌊(10³π mod 1) · 10⌋ = 5.

Dabei bezeichnet mod 1 den gebrochenen Teil und ⌊·⌋ die Gauß-Klammer, also das Abrunden auf die größte ganze Zahl.

Für die n-te Stelle der Hexadezimaldarstellung π = ∑_{k=0}^{∞} zₖ/16ᵏ gilt entsprechend:

zₙ = ⌊(16ⁿ⁻¹π mod 1) · 16⌋.

Multipliziert man die BBP-Formel mit 16ⁿ⁻¹ und fasst die vier Bestandteile zusammen, erhält man 16ⁿ⁻¹π = 4σ₁ − 2σ₄ − σ₅ − σ₆ mit

σₜ = ∑_{k=0}^{∞} 16ⁿ⁻ᵏ⁻¹/(8k+t).

Für die Berechnung des gebrochenen Teils können bei den ersten n Summanden ganzzahlige Anteile entfernt werden. Dazu wird der Zähler modulo 8k+t genommen. Die restlichen Summanden ab k ≥ n besitzen keinen ganzzahligen Anteil. Damit gilt modulo 1:

σₜ ≡ σ′ₜ = ∑{k=0}^{n−1} [16ⁿ⁻ᵏ⁻¹ mod (8k+t)]/(8k+t) + ∑{k=n}^{∞} 16ⁿ⁻ᵏ⁻¹/(8k+t).

Die Potenzen im Zähler der ersten Summe werden effizient mit binärer Exponentiation berechnet. Dabei bleiben die Zwischenergebnisse kleiner als 64n². Schließlich wird auch von der Linearkombination der vier Summen der ganzzahlige Teil entfernt:

zₙ = ⌊((4σ′₁ − 2σ′₄ − σ′₅ − σ′₆) mod 1) · 16⌋.

Polylogarithmische Konstanten und BBP-Reihen

Nach der Entdeckung der BBP-Formel wurden viele ähnliche Reihen der Form

α = ∑_{k=0}^{∞} p(k)/(bᵏq(k))

gefunden. Sie ergeben andere fundamentale mathematische Konstanten in einer Darstellung zur Basis b. Beispiele sind die polylogarithmischen Konstanten π² und ζ(3) sowie die Catalansche Konstante G. Solche Formeln werden BBP-Reihen zur Basis b genannt.

Bislang ist unbeantwortet, zu welchen mathematischen Konstanten BBP-Reihen existieren. Für die Logarithmen bestimmter Primzahlen p sind BBP-Reihen bekannt. Die im Artikel aufgeführte Liste beginnt mit:

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, 268501, 279073, 312709, …

23, 47, 53 und 59 sind die kleinsten Primzahlen, die in dieser Liste fehlen. Es ist jedoch unbewiesen, ob für log 23 tatsächlich keine BBP-Reihe existiert. Vermutlich gibt es für die Quadratwurzeln √2, √3, √5, …, für die Eulersche Zahl e und für die Eulersche Konstante γ keine BBP-Reihen, weil diese Konstanten vermutlich nicht polylogarithmisch sind.

Vorteile des Verfahrens

Der BBP-Algorithmus berechnet nur die jeweils benötigte Stelle von π. Deshalb muss kein Speicherplatz für die vorherigen Stellen reserviert werden. Für die gespeicherten Ziffern können außerdem einfachere Datentypen verwendet werden; diese ermöglichen kürzere Zugriffszeiten. Dadurch ist das Verfahren schneller und machte in vielen Anwendungen frühere Algorithmen zur Berechnung von π überflüssig, da diese größere und komplexere Datentypen benötigten.

Die Bellard-Formel

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

π = ∑_{k=0}^{∞} [(-1)ᵏ/2¹⁰ᵏ⁺⁶] · (2⁸/(10k+1) − 2⁶/(10k+3) − 2⁵/(4k+1) − 2²/(10k+5) − 2²/(10k+7) + 1/(10k+9) − 1/(4k+3)).