www.wikidata.de-de.nina.az

Bailey Borwein Plouffe Formel In der Mathematik bezeichnet die BBP Formel eine 1995 vom kanadischen Mathematiker Simon P

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:

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 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:

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 ( (Memento des Originals vom 10. Juni 2011 im Internet Archive) [abgerufen am 30. Oktober 2008]).
  2. Folge A104885 in OEIS

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Mathematik bezeichnet die Bailey Borwein Plouffe Formel BBP Formel eine 1995 vom kanadischen Mathematiker Simon Plouffe entdeckte Summenformel zur Berechnung der Kreiszahl p displaystyle pi Die von Plouffe entdeckte Reihe fur p displaystyle pi ist p k 0 1 16 k 4 8 k 1 2 8 k 4 1 8 k 5 1 8 k 6 displaystyle 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 veroffentlicht 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 p displaystyle pi im Hexadezimalsystem ohne Berechnung der vorherigen Ziffern ermittelt Ziffer Extraktion Inhaltsverzeichnis 1 Polylogarithmische Konstante 2 BBP Algorithmus 3 Vorteile des BBP Algorithmus 4 Bellard Formel 5 Literatur 6 Einzelnachweise 7 WeblinksPolylogarithmische Konstante BearbeitenSeit Plouffes Entdeckung wurden viele ahnliche Formeln der Gestalt a k 0 p k b k q k displaystyle alpha sum k 0 infty frac p k b k q k nbsp entdeckt die sich zu anderen fundamentalen mathematischen Konstanten in der Darstellung zur Basis b displaystyle b nbsp aufsummieren wie z B zu den polylogarithmischen Konstanten p 2 z 3 displaystyle pi 2 zeta 3 nbsp und zur Catalanschen Konstanten G displaystyle G nbsp Man bezeichnet diese Formeln als BBP Reihen zur Basis b displaystyle b nbsp Die Frage zu welchen mathematischen Konstanten BBP Reihen existieren ist bislang unbeantwortet Zu folgenden Primzahlen p displaystyle p nbsp existiert fur log p displaystyle log p nbsp 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 log 23 displaystyle log 23 nbsp tatsachlich keine BBP Reihe existiert Vermutlich gibt es fur Quadratwurzeln 2 3 5 displaystyle sqrt 2 sqrt 3 sqrt 5 dotsc nbsp die Eulersche Zahl e displaystyle e nbsp und die Eulersche Konstante g displaystyle gamma nbsp keine BBP Reihe da das vermutlich keine polylogarithmischen Konstanten sind BBP Algorithmus BearbeitenAn einem Beispiel soll gezeigt werden wie man die Ziffern einer Zahlendarstellung erhalt So bekommt man z B die 4 dezimale Nachkommastelle von p displaystyle pi nbsp durch Multiplikation mit 10 3 displaystyle 10 3 nbsp 10 3 p 3141 592 6 displaystyle 10 3 pi 3141 5926 ldots nbsp Wegschneiden des ganzzahligen Teils 10 3 p mod 1 0 592 6 displaystyle 10 3 pi bmod 1 0 5926 ldots nbsp Multiplikation mit 10 displaystyle 10 nbsp 10 3 p mod 1 10 5 926 displaystyle 10 3 pi bmod 1 cdot 10 5 926 ldots nbsp und Wegschneiden des gebrochenen Teils 10 3 p mod 1 10 5 displaystyle lfloor 10 3 pi bmod 1 cdot 10 rfloor 5 nbsp wobei zur Notation der Modulo Operator und die Gauss Klammer verwendet werden Analog ergibt sich die n displaystyle n nbsp te Stelle der Hexadezimaldarstellung k 0 z k 16 k displaystyle sum k 0 infty frac z k 16 k nbsp von p displaystyle pi nbsp zu z n 16 n 1 p mod 1 16 displaystyle z n lfloor 16 n 1 pi bmod 1 cdot 16 rfloor nbsp Multiplikation der Plouffe Formel mit 16 n 1 displaystyle 16 n 1 nbsp ergibt nach Unterteilung in vier Terme 16 n 1 p 4 s 1 2 s 4 s 5 s 6 mit s t k 0 16 n k 1 8 k t 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 nbsp Da im Ausdruck fur z n displaystyle z n nbsp nur der gebrochene Teil von 16 n 1 p displaystyle 16 n 1 pi nbsp eingeht kann man bei der Berechnung der s t displaystyle sigma t nbsp einen ganzzahligen Teil von den ersten n displaystyle n nbsp Summanden entfernen um die Grosse der Zwischenergebnisse zu begrenzen Das erreicht man durch Anwendung des Operators mod 8 k t displaystyle bmod 8k t nbsp auf den Zahler Die restlichen Summanden mit k n displaystyle k geq n nbsp haben keinen ganzzahligen Teil Damit erhalt man unter Verwendung des Zeichens displaystyle equiv nbsp fur Kongruenz s t s t k 0 n 1 16 n k 1 mod 8 k t 8 k t k n 16 n k 1 8 k t mod 1 displaystyle 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 nbsp Die diskrete Exponentialfunktion im Zahler der ersten Summe kann man mit der binaren Exponentiation effizient berechnen wobei die Zwischenergebnisse kleiner als 64 n 2 displaystyle 64n 2 nbsp bleiben Damit gilt 16 n 1 p 4 s 1 2 s 4 s 5 s 6 mod 1 displaystyle 16 n 1 pi equiv 4 sigma 1 2 sigma 4 sigma 5 sigma 6 pmod 1 nbsp Da die s t displaystyle sigma t nbsp und ihre Linearkombination noch einen ganzzahligen Teil enthalten konnen muss dieser noch entfernt werden Somit ist z n 4 s 1 2 s 4 s 5 s 6 mod 1 16 displaystyle z n lfloor 4 sigma 1 2 sigma 4 sigma 5 sigma 6 bmod 1 cdot 16 rfloor nbsp Vorteile des BBP Algorithmus BearbeitenDiese Methode nur die gerade benotigte Stelle von p displaystyle pi nbsp zu extrahieren erspart den Speicherplatz fur die vorherigen Stellen Weiter kann man einfachere Datentypen fur die Speicherung der gewonnenen Stellen verwenden die wiederum auch kurzere Zugriffszeiten haben was den Algorithmus letztlich schneller macht Daher hat diese Methode in vielen Anwendungen alle vorherigen Algorithmen zur Berechnung von p displaystyle pi nbsp die grossere und komplexere Datentypen benotigten uberflussig gemacht Bellard Formel Bearbeiten Hauptartikel Bellard Formel Fabrice Bellard entdeckte diese ahnliche Formel 1997 Sie ist etwa 43 schneller als BBP p k 0 1 k 2 10 k 6 2 8 10 k 1 2 6 10 k 3 2 5 4 k 1 2 2 10 k 5 2 2 10 k 7 1 10 k 9 1 4 k 3 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 nbsp Literatur BearbeitenMarc 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 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 Folge A104885 in OEISWeblinks BearbeitenDavid H Bailey Personliche Webseite Eine ausfuhrliche Anleitung mit konkretem Beispiel Memento vom 10 April 2014 imInternet Archive Implementierung in Python Memento vom 16 November 2015 imInternet Archive Abgerufen von https de wikipedia org w index php title Bailey Borwein Plouffe Formel amp oldid 233061431