π und e: Tröpfel-Algorithmen

Diese HTML-Seite enthält ein JavaScript-Programm, welches live und vor Ihren Augen die Kreiszahl π und die Euler'sche Zahl e nach dem Tröpfel-Algorithmus von Rabinowitz & Wagon (1995) berechnet.

Berechne:
Basis:
Anzahl Ziffern:
Erläuterung

Die Kreiszahl π ebenso wie die Eulersche Zahl e ist ein unendlicher nichtperiodischer Dezimalbruch - um sie mit einer vorgegebenen Genauigkeit zu berechnen und darzustellen werden daher meistens Programme benutzt, die mit reellen Zahlen großer oder beliebiger Länge arbeiten können. Dazu sind dann ausgeklügelte Algorithmen erforderlich, welche die vier Grundrechenarten (insbesondere die Multiplikation) erheblich effizienter ausführen als die in der Schule gelehrten Methoden.

Der Tröpfel-Algorithmus ist eine erstaunliche Ausnahme: er verwendet nur ganze Zahlen in der in normalen Programmiersprachen üblichen Genauigkeit, so daß keine Spezialprogrammierung notwendig ist. Er spuckt die Ziffern eine nach der anderen aus und verwendet die bereits berechneten Ziffern danach nicht mehr weiter.

Im folgenden wird das Prinzip des Tröpfel-Algorithmus kurz skizziert.

Mixed Radix Zahlensysteme

Reelle Zahlen werden normalerweise als Dezimalbrüche dargestellt, die eine Kurzschreibweise einer Reihenentwicklung sind, z.B.:

3,141592653...=3*1 + 1*1/10 + 4*1/100 + 1*1/1000 + 5*1/10000 + ...

              =3+1/10*(1+1/10*(4+1/10*(1+ ... ))))

In diesem Beispiel wird als Basis-Sequenz (1/10, 1/10, 1/10, ...) verwendet. Man kann Zahlen jedoch auch mit einer gemischten Basis-Sequenz (engl. mixed radix) darstellen. Die gemischte basis b=(1/2, 1/3, 1/4, 1/5, ...) würde Zahlen durch den Ausdruck


a0+1/2*(a1+1/3*(a2+1/4*(a3+ ... ))))


beschreiben.

Falls es eine gemischte Basis-Sequenz gibt, in der π oder e durch eine einem einfachen Gesetz gehorchenden Ziffernfolge ausgedrückt werden kann, dann kann man die dezimale Ziffernfolge durch eine einfache Basisumwandlung daraus ableiten. Genau das tut der Tröpfel-Algorithmus.

Die Darstellung von Pi

Der Tröpfel-Algorithmus basiert auf der Reihenentwicklung

π/2 = 1 + 1/3 + 1*2/3*5 + 1*2*3/3*5*7 + ...

Diese kann auch geschrieben werden als

π/2 = 1+1/3*(1+2/5*(1+3/7*(1+4/9*(1+ ... ))))

Diese Darstellung entspricht nach Multiplikation beider Seiten mit 2 der Ziffernfolge 2,22222... mit der mixed radix c=(1/3, 2/5, 3/7, 4/9, ...)

Die Darstellung von e

Der Tröpfel-Algorithmus basiert auf der Reihenentwicklung

 e=1/1! + 1/2! + 1/3! + 1/4!...

Diese kann auch geschrieben werden als

1+1/1(1+1/2(+1/3(1+1/4(1+1/5(1+ ...)))))

Diese Darstellung entspricht nach Multiplikation beider Seiten mit 2 der Ziffernfolge 2,111111... mit der mixed radix c=(1/1, 1/2, 1/3, 1/4, 1/5, ...)

Literatur
Stanley Rabinowitz, Stan Wagon (1995):
A Spigot Algorithm for the Digits of pi, American Mathematical Monthly,vol. 102,No. 3,195-203
Stewart, Ian (1995):
Tröpfel-Algorithmen,Spektrum der Wissenschaft,Dezember 1995,10-14 (Anmerkung: die Beschreibung des Algorithmus für π in diesem Artikel ist nicht ganz korrekt, der Fehler wurde in diesem Programm aber behoben.)

Implementierung: Dr. Martin Knapmeyer, Dez. 1995 (π, Pascal, Atari) & Aug. 2004 (JavaScript, e)


eof.