Tröpfelalgorithmus

Als Tröpfelalgorithmus bezeichnet man einen Algorithmus zur Berechnung mathematischer Konstanten wie der Kreiszahl $\pi$ oder der eulerschen Zahl $e$, bei dem die Ziffern eine nach der anderen berechnet und anschließend nicht mehr benötigt werden, also sozusagen herauströpfeln. Solche Algorithmen kommen bei der Berechnung häufig mit kleinen ganzen Zahlen aus, eine Implementierung hat damit keine Probleme mit Rundungsfehlern und benötigt keine Langzahlarithmetik. Als erster Algorithmus dieses Typs gilt ein Algorithmus zur Berechnung der eulerschen Zahl, den A. H. J. Sale 1968 veröffentlichte. Der englische Name spigot algorithm (wörtlich: Zapfhahnalgorithmus) taucht erstmals 1991 bei Stanley Rabinowitz auf, der einen Tröpfelalgorithmus für $\pi$ angab.

Grundprinzip

Tröpfelalgorithmen beruhen auf folgendem einfachen Algorithmus zur Bestimmung der Ziffern:

1. Bestimme den ganzzahligen Teil der Zahl und notiere ihn.
2. Ersetze die Zahl durch den gebrochenen Teil, ziehe also den ganzzahligen Teil ab.
3. Multipliziere mit 10.

Wiederholt man diese Schritte, so ergibt sich im ersten Schritt der Teil vor dem Komma, in allen weiteren Schritten die nächste Nachkommaziffer. Multipliziert man statt mit 10 mit einer anderen Zahl, so ergibt sich die Darstellung nicht im Dezimalsystem, sondern analog in jedem beliebigen Stellenwertsystem.

Häufig beruhen Tröpfelalgorithmen auf gemischten Basen. Während die übliche Darstellung der eulerschen Zahl $e=2{,}718\dots$ letztlich eine konventionelle Schreibweise ist für

$e=2+{\tfrac {1}{10}}(7+{\tfrac {1}{10}}(1+{\tfrac {1}{10}}(8+\dots )))$,

so lässt sich aus der Formel $\textstyle e=\sum _{n=0}^{\infty }{\frac {1}{n!}}$ folgende Darstellung gewinnen:

$e=2+{\tfrac {1}{2}}(1+{\tfrac {1}{3}}(1+{\tfrac {1}{4}}(1+\dots )))$

Hierbei handelt es sich um eine Erweiterung des fakultätsbasierten Zahlensystems auf reelle Zahlen, in dem die eulersche Zahl geschrieben werden kann als $e=2{,}111\dots$.

In dieser Darstellung lassen sich der ganzzahlige und gebrochene Teil einer Zahl ebenso leicht bestimmen wie im gewöhnlichen Dezimalsystem, indem man den Teil vor und nach dem Komma nimmt. Auch die Multiplikation lässt sich wie üblich durchführen, lediglich beim Übertrag ist die gemischte Basis zu beachten.

Tröpfelalgorithmus für die eulersche Zahl

Aus dieser Idee ergibt sich der folgende Algorithmus zur Berechnung von $n$ Nachkommastellen der eulerschen Zahl im Dezimalsystem:

1. Bestimme $m$ so, dass $m!$ mindestens $n$ Stellen besitzt.
2. Notiere zwei Zeilen A und B mit je $m$ Spalten. Die erste Spalte bleibt jeweils frei, Zeile A wird mit $m-1$ Zahlen 1 gefüllt, Zeile B mit den Zahlen von 2 bis $m$.
3. Notiere eine weitere Zeile, in der ersten Spalte eine 2, anschließend $m-1$ Mal die 1. Die 2 ist bereits die Ziffer vor dem Komma.
4. Füge eine weitere Zeile unten an, und fülle sie mit den folgenden Schritten von rechts nach links:
   1. Bestimme die nächste Zahl durch folgende Schritte:
      1. Multipliziere die Zahl, die in der aktuellen Spalte in der vorherigen Zeile steht mit 10 und addiere den Übertrag von der vorherigen Spalte (für die Spalte rechts außen ist der Übertrag 0).
      2. Dividiere das Ergebnis mit Rest durch die Zahl, die in der Zeile B steht, und notiere den Rest.
      3. Multipliziere den Quotienten mit der Zahl aus der Zeile A, dies ist der Übertrag für die nächste Spalte. (Da die Zahl in Zeile A hier immer eine 1 ist, kann die Multiplikation auch entfallen.) Wiederhole Schritt 4.1, bis die zweite Spalte gefüllt ist.
   2. Notiere den Übertrag aus der zweiten Spalte in der ersten Spalte, es ist die nächste Ziffer von $e$. Wiederhole Schritt 4, bis du $n$ Stellen berechnet hast.

Beispiel

Das folgende Beispiel führt den Algorithmus zur Berechnung von 4 Nachkommastellen durch, wobei $m=7$ gewählt wird, weil $7!=5040$ die nötigen 4 Stellen zur Anwendung dieses Tröpfelalgorithmus hat:

A		1	1	1	1	1	1
B		2	3	4	5	6	7
	2	1	1	1	1	1	1
	7	0	1	0	1	5	3
	1	1	1	3	4	0	2
	8	0	1	2	0	2	6
	2	1	0	0	4	4	4

Die 3 in der vierten Zeile rechts außen ergibt sich dabei als der Rest von 10 bei Division durch 7. Dies ergibt einen Übertrag 1, sodass in der nächsten Spalte 11 durch 6 dividiert wird, was als Rest 5 und als Übertrag 1 ergibt. Entsprechend werden die weiteren Einträge berechnet.

Tröpfelalgorithmus für π

Einen ähnlichen Algorithmus fand Stanley Rabinowitz für die Berechnung von $\pi$. Er beruht auf einer gemischten gebrochenen Basis, es gilt:

$\pi =2+{\tfrac {1}{3}}(2+{\tfrac {2}{5}}(2+{\tfrac {3}{7}}(2+\dots )))$

Bezüglich der gemischten gebrochenen Basis $(1;{\tfrac {1}{3}},{\tfrac {2}{5}},{\tfrac {3}{7}},\dots )$ gilt also $\pi =2{,}222\dots$

Hier kommt die Schwierigkeit hinzu, dass der „Nachkommateil“ größer werden kann als 1, sodass sich ganzzahliger und gebrochener Teil nicht mehr so leicht bestimmen lassen. Dies führt zu folgendem Algorithmus, um $n$ Nachkommastellen von $\pi$ zu bestimmen:

1. Bestimme $m$ hinreichend groß, meist genügt $m=\lfloor 10(n+1)/3\rfloor$.
2. Notiere zwei Zeilen A und B mit je $m$ Spalten. Die erste Spalte bleibt jeweils frei, Zeile A wird mit den Zahlen von 1 bis $m-1$ gefüllt, Zeile B mit den ungeraden Zahlen von 3 bis $2m-1$.
3. Notiere eine weitere Zeile mit $m$ Mal der Zahl 2.
4. Füge eine weitere Zeile unten an, und fülle sie mit den folgenden Schritten von rechts nach links:
   1. Bestimme die nächste Zahl durch folgende Schritte:
      1. Multipliziere die Zahl, die in der aktuellen Spalte in der vorherigen Zeile steht mit 10 und addiere den Übertrag von der vorherigen Spalte (für die Spalte rechts außen ist der Übertrag 0).
      2. Dividiere das Ergebnis mit Rest durch die Zahl, die in der Zeile B steht, und notiere den Rest.
      3. Multipliziere den Quotienten mit der Zahl aus der Zeile A, dies ist der Übertrag für die nächste Spalte. Wiederhole Schritt 4.1, bis die zweite Spalte gefüllt ist.
   2. Multipliziere den Eintrag der ersten Spalte aus der vorherigen Zeile mit 10 und addiere den Übertrag aus der zweiten Spalte.
   3. Dividiere das Ergebnis mit Rest durch 10 und notiere den Rest in der ersten Spalte.
   4. Der Quotient ist die nächste vorläufige Ziffer. Sie kann im Bereich von 0 bis 10 liegen. Führe je nach ihrer Größe einen der folgenden Schritte durch:
      • 0–8: Gib alle bisherigen vorläufigen Ziffern aus und behalte nur die neue.
      • 9: Hänge die neue Ziffer an die bisherigen vorläufigen Ziffern an.
      • 10: Erhöhe alle bisherigen vorläufigen Ziffern um 1 (aus 9 wird 0) und gib sie aus. Neue vorläufige Ziffer ist die 0.
   5. Wiederhole Schritt 4, bis du $n$ Stellen berechnet hast.

Beispiel

Das folgende Beispiel führt den Algorithmus zur Berechnung von $n=3$ Nachkommastellen durch; dafür ist die Anzahl der erforderlichen Spalten $m=\lfloor 10(3+1)/3\rfloor =13$:

A		1	2	3	4	5	6	7	8	9	10	11	12
B		3	5	7	9	11	13	15	17	19	21	23	25
	2	2	2	2	2	2	2	2	2	2	2	2	2
3	0	2	2	4	3	10	1	13	12	1	20	20	20
1	3	1	3	3	5	5	4	8	5	8	17	20	0
4	1	1	0	0	0	4	12	9	4	10	6	16	0
1	4	0	4	3	1	3	1	3	10	8	0	22	0

Tatsächlich kann man nicht sicher sein, dass die dritte Nachkommastelle eine 1 ist, es könnte passieren, dass sie im nächsten Schritt noch auf 2 erhöht werden müsste. In Wirklichkeit tritt dieser Fall erstmals an der 31. Nachkommastelle auf, hier liefert der Algorithmus zunächst 4, erst im nächsten Schritt wird sie zu 5 korrigiert. Man kann dieses Problem teilweise umgehen, indem man eine Ziffer mehr berechnet (und $m$ entsprechend größer wählt), allerdings kann es auch in diesem Fall passieren, dass man weniger gesicherte Ziffern erhält als gewünscht, nämlich dann, wenn am Ende eine Kette aus 9 vorliegt. Falls $\pi$ normal ist, so muss im Durchschnitt eine von 20 vorläufigen Ziffern nachträglich korrigiert werden.

Weitere Tröpfelalgorithmen

Auch für andere Zahlen lassen sich Tröpfelalgorithmen finden. Eine Reihe besonderer Algorithmen zur Berechnung von $\pi$ fand Jeremy Gibbons. Während man beim obigen Algorithmus zu Beginn die Zahl der gewünschten Stellen festlegen muss (er ist bounded, also beschränkt), kann der Algorithmus von Gibbons von festen Startwerten aus beliebig lange ausgeführt werden, um beliebig viele Ziffern zu erhalten (unbounded, also unbeschränkt).

Literatur

• Jörg Arndt, Christoph Haenel: Pi. Algorithmen, Computer, Arithmetik. Springer, 2. Auflage 2000. ISBN 978-3-540-66258-7.
• Ian Stewart: Tröpfel-Algorithmen. Spektrum der Wissenschaft 12 / 1995, Seite 10. (online)

Weblinks

• Tröpfel-Algorithmen, mit Implementierungen
• Algorithmen, mit ausführlichen Erläuterungen
• Eric W. Weisstein: Spigot algorithm. In: MathWorld (englisch).