Bailey-Borwein-Plouffe-Formel

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

In der Mathematik bezeichnet die Bailey-Borwein-Plouffe-Formel (BBP-Formel) eine 1995 von Simon Plouffe entdeckte Summenformel zur Berechnung der Kreiszahl $π$ . Seitdem wurden viele ähnliche Formeln der Gestalt

$\alpha = \sum_{k = 0}^{\infty} \frac{p(k)}{b^kq(k)}$

entdeckt, die sich zu anderen fundamentalen irrationalen Konstanten (in der Darstellung zur Basis b) aufsummieren, wie z.B. zur Catalanschen Konstanten G. Man bezeichnet diese Formeln als BBP-typ Formeln.

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)$

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. Man nennt dies Ziffer-Extraktion.

Die Frage, zu welchen mathematischen Konstanten BBP-Reihen existieren ist bislang unbeantwortet. Es ist unklar, ob zur Eulerschen Zahl e oder zu der polylogarithmischen Konstanten log 23 BBP-Reihen existieren.

[Bearbeiten] BBP-Algorithmus

Um eine Ziffer extrahieren zu können, muss man die obige Formel umschreiben:

$\pi = 4 \sum_{k = 0}^{\infty} \frac{1}{16^k (8k+1)} - 2 \sum_{k = 0}^{\infty} \frac{1}{16^k (8k+4)} - \sum_{k = 0}^{\infty} \frac{1}{16^k (8k+5)} - \sum_{k = 0}^{\infty} \frac{1}{16^k(8k+6)}$

Wir interessieren uns für die n-te hexadezimale Ziffer von $π$ , also $z n$ in

$\pi = \sum_{k = 1}^{\infty} Z_k 16^k + \sum_{k = 0}^{\infty} \frac {z_k}{16^k} = \sum_{k = 0}^{\infty} \frac {z_k}{16^k} \quad (\pi < 16)$ ,

deshalb spalten wir die Summen nach dem n-ten Glied auf, z.B. die erste zu:

$\sigma_1 = \sum_{k = 0}^{\infty} \frac{1}{16^k (8k+1)} = \sum_{k = 0}^{n} \frac{1}{16^k (8k+1)} + \sum_{k = n + 1}^{\infty} \frac{1}{16^k (8k+1)}$

Nun multiplizieren wir mit $16 n$ , damit das Hexadezimalkomma (der Trenner zwischen ganzzahligem und gebrochenen Anteil der Zahl) an der richtigen Stelle steht:

$16^n \sigma_1 = \sum_{k = 0}^{\infty} \frac{16^{n-k}}{8k+1} = \sum_{k = 0}^{n} \frac{16^{n-k}}{8k+1} + \sum_{k = n + 1}^{\infty} \frac{16^{n-k}}{8k+1}$

Da wir nur an dem gebrochenen Anteil der Summe interessiert sind, schauen wir uns beide Teilsummen an und uns wird klar, dass nur die erste Summe in der Lage ist, ganze Zahlen zu erzeugen, wohingegen die zweite Summe keine ganzen Zahlen erzeugen kann, weil der Zähler niemals größer, als der Nenner werden kann (für k > n). Deshalb brauchen wir einen Trick, um die ganzen Zahlen aus der ersten Summe zu entfernen. Dieser Trick ist $\mbox{mod}\,8k+1$ .

Für den k-ten Summanden gilt:

$\frac{16^{n-k}}{8k+1} = \frac{d_k (8k+1) + (16^{n-k} \mbox{mod}\,8k+1)}{8k+1} = d_k + \frac{16^{n-k} \mbox{mod}\,8k+1}{8k+1}$

mit ganzzahligem Anteil $d k$ , woraus folgt:

$\frac{16^{n-k}}{8k+1} - d_k = \frac{16^{n-k} \mbox{mod}\,8k+1}{8k+1} < 1$

D.h. der Modulo-Operator sorgt dafür, dass nur der gebrochene Anteil der Summe erhalten bleibt.

Die Summe für den ersten gebrochenen Anteil wird dann zu:

$16^n \sigma_1 \cong \sum_{k = 0}^{n} \frac{16^{n-k} \mbox{mod}\,8k+1}{8k+1} + \sum_{k = n + 1}^{\infty} \frac{16^{n-k}}{8k+1}$

Um nun die Berechnung abzuschließen, muss man diese Prozedur auf jeden der vier Summanden jeweils anwenden. Schließlich setzt man die Resultate in die Summe für $π$ ein:

$16^n \pi \cong 4 \sigma_1 - 2 \sigma_2 - \sigma_3 - \sigma_4$

Man darf nicht vergessen, dass nur der gebrochene Anteil korrekt ist, um die gewünschte Ziffer extrahieren zu können, muss man daher den ganzzahligen Anteil der Endsumme entfernen und mit $16$ multiplizieren. (Theoretisch sollten noch ein paar weitere Ziffern korrekt sein).

[Bearbeiten] Weblinks

[Bearbeiten] 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.

Von „http://de.wikipedia.org../../../b/a/i/Bailey-Borwein-Plouffe-Formel_6a88.html“

Kategorien: Zahl | Folgen und Reihen