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 π.

Die von Plouffe entdeckte Reihe für π 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 des Zeitschriftenartikels benannt, in dem die Formel erstmals veröffentlicht wurde, David H. Bailey, Peter Borwein und Plouffe.[1] Das Erstaunliche an dieser speziellen Formel ist, dass man mit ein wenig Umstellen einen Algorithmus daraus ableiten kann, der eine beliebige Ziffer der Darstellung von π im Hexadezimalsystem bestimmen kann, ohne die vorherigen Ziffern zu benötigen (Ziffer-Extraktion).

Inhaltsverzeichnis

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: (Sloane A104885)

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 γ 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 π durch

  • Multiplikation mit 103
 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 von π

\pi = \sum_{k = 0}^{\infty} \frac {z_k}{16^k}\quad \text{ als } \quad
   z_n=\lfloor(16^{n-1}\pi\,\bmod\, 1)\times 16\rfloor

Multiplikation mit 16n − 1 der Plouffe-Formel 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 zn nur der gebrochene Teil von 16n − 1π eingeht, entfernen wir zunächst von jedem einzelnen Summanden den ganzzahligen Teil. In den ersten n Summanden von σl erreichen wir dies durch Anwendung des Operators mod(8k + l) auf den Zähler, die restlichen Summanden mit k\geq n haben keinen ganzzahligen Teil. Damit ändert sich σl ab auf

\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 ist unter Verwendung des Zeichens \equiv für Kongruenz

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

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 zn zu erhalten.

Vorteile des BBP-Algorithmus

Diese Methode, nur die gerade benötigte Stelle von π 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 π (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
  • David H. Bailey. A Compendium of BBP-Type Formulas for Mathematical Constants, 2004, online
  • Barry Cipra. Digits of Pi in D.Mackenzie, B.Cipra (eds). What's happening in the Mathematical Sciences Vol.6, pp29-39. AMS 2006.

Einzelnachweise

  1. Bailey, David H., Borwein, Peter B., and Plouffe, Simon: On the Rapid Computation of Various Polylogarithmic Constants. In: Mathematics of Computation. 66, Nr. 218, April 1997, S. 903–913. doi:10.1090/S0025-5718-97-00856-9.

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bailey — steht für Bailey (Familienname) – dort auch Namensträger Bailey (Automarke), US amerikanischer Automobilhersteller Bailey heißen folgende Orte: in Kanada: Bailey (New Brunswick) in den Vereinigten Staaten: Bailey (Arkansas) Bailey (Colorado)… …   Deutsch Wikipedia

  • David H. Bailey — David Harold Bailey (* 1948) ist ein US amerikanischer Mathematiker und Informatiker. Nach seinem Abschluss an der Brigham Young University (1972) promovierte er 1976 bei Donald Ornstein an der Stanford University mit der Arbeit Sequential… …   Deutsch Wikipedia

  • Peter Borwein — Peter Benjamin Borwein (* 5. Oktober 1953 in St Andrews)[1] ist ein kanadischer Mathematiker, der als Mit Entdecker der Bailey Borwein Plouffe Formel (nach D. Bailey, P. Borwein und S. Plouffe) zur Berechnung einer beliebigen hexadezimalen Stelle …   Deutsch Wikipedia

  • Simon Plouffe — (* 11. Juni 1956 in Saint Jovite, Québec) ist ein kanadischer Mathematiker. Plouffe entdeckte 1995 die dem BBP Algorithmus zugrunde liegende Formel (die Bailey Borwein Plouffe Formel), welche die Extraktion der n ten Ziffer der Binärentwicklung… …   Deutsch Wikipedia

  • 3,14 — Der griechische Buchstabe Pi Ein Kreis mit einem Durchmesser von 1 hat einen Umfang von π. Die Kreiszahl π (Pi) ist eine …   Deutsch Wikipedia

  • Ludolfsche Zahl — Der griechische Buchstabe Pi Ein Kreis mit einem Durchmesser von 1 hat einen Umfang von π. Die Kreiszahl π (Pi) ist eine …   Deutsch Wikipedia

  • Ludolphsche Zahl — Der griechische Buchstabe Pi Ein Kreis mit einem Durchmesser von 1 hat einen Umfang von π. Die Kreiszahl π (Pi) ist eine …   Deutsch Wikipedia

  • Pi (Kreiszahl) — Der griechische Buchstabe Pi Ein Kreis mit einem Durchmesser von 1 hat einen Umfang von π. Die Kreiszahl π (Pi) ist eine …   Deutsch Wikipedia

  • Pi (Zahl) — Der griechische Buchstabe Pi Ein Kreis mit einem Durchmesser von 1 hat einen Umfang von π. Die Kreiszahl π (Pi) ist eine …   Deutsch Wikipedia

  • Kreiszahl — Der griechische Buchstabe Pi Ein Kreis mit einem Durchmess …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”