Bailey-Borwein-Plouffe-Formel

Summenformel zur Berechnung der Kreiszahl

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:

Die Formel ist nach den Autoren David H. Bailey, Peter Borwein und Simon Plouffe des Zeitschriftenartikels benannt, in dem sie erstmals veröffentlicht wurde.[1] 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 im Hexadezimalsystem ohne Berechnung der vorherigen Ziffern ermittelt (Ziffer-Extraktion).

Polylogarithmische Konstante

Bearbeiten

Seit Plouffes Entdeckung wurden viele ähnliche Formeln der Gestalt

 

entdeckt, die sich zu anderen fundamentalen mathematischen Konstanten (in der Darstellung zur Basis  ) aufsummieren, wie z. B. zu den polylogarithmischen Konstanten   und zur Catalanschen Konstanten  . Man bezeichnet diese Formeln als BBP-Reihen zur Basis  . Die Frage, zu welchen mathematischen Konstanten BBP-Reihen existieren, ist bislang unbeantwortet. Zu folgenden Primzahlen   existiert für   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, …[2]

23, 47, 53 und 59 sind die kleinsten Primzahlen, die in dieser Liste fehlen. Es ist jedoch unbewiesen, ob zu   tatsächlich keine BBP-Reihe existiert. Vermutlich gibt es für Quadratwurzeln  , die Eulersche Zahl   und die Eulersche Konstante   keine BBP-Reihe, da das (vermutlich) keine polylogarithmischen Konstanten sind.

BBP-Algorithmus

Bearbeiten

An einem Beispiel soll gezeigt werden, wie man die Ziffern einer Zahlendarstellung erhält. So bekommt man z. B. die 4. dezimale Nachkommastelle von   durch

  • Multiplikation mit  
   
  • Wegschneiden des ganzzahligen Teils …
   
  • Multiplikation mit  
   
  • und Wegschneiden des gebrochenen Teils …
   

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

Analog ergibt sich die  -te Stelle der Hexadezimaldarstellung   von   zu

 

Multiplikation der Plouffe-Formel mit   ergibt nach Unterteilung in vier Terme

 

Da im Ausdruck für   nur der gebrochene Teil von   eingeht, kann man bei der Berechnung der   einen ganzzahligen Teil von den ersten   Summanden entfernen, um die Größe der Zwischenergebnisse zu begrenzen. Das erreicht man durch Anwendung des Operators   auf den Zähler. Die restlichen Summanden mit   haben keinen ganzzahligen Teil. Damit erhält man (unter Verwendung des Zeichens   für Kongruenz):

 .

Die diskrete Exponentialfunktion im Zähler der ersten Summe kann man mit der binären Exponentiation effizient berechnen, wobei die Zwischenergebnisse kleiner als   bleiben. Damit gilt

 .

Da die   und ihre Linearkombination noch einen ganzzahligen Teil enthalten können, muss dieser noch entfernt werden. Somit ist

 

Vorteile des BBP-Algorithmus

Bearbeiten

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

Bellard-Formel

Bearbeiten

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

 .

Literatur

Bearbeiten
  • 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.

Einzelnachweise

Bearbeiten
  1. David H. Bailey, Peter B. Borwein, Simon Plouffe: On the Rapid Computation of Various Polylogarithmic Constants. In: Mathematics of Computation. 66. Jahrgang, Nr. 218, April 1997, S. 903–913, doi:10.1090/S0025-5718-97-00856-9 (crd.lbl.gov (Memento des Originals vom 10. Juni 2011 im Internet Archive) [abgerufen am 30. Oktober 2008]).
  2. Folge A104885 in OEIS
Bearbeiten