Direkt zum Inhalt

Lexikon der Mathematik: Tröpfelalgorithmus

Verfahren zur Berechnung eines Näherungswertes zu einer Zahl, das die Dezimalstellen eine nach der anderen liefert, also sozusagen ‚herauströpfelt‘.

Beispielsweise erhält man aus \(e=\displaystyle {\sum}_{n=1}^{\infty}\frac{1}{n!}\) die Darstellung \begin{eqnarray}e=1+\frac{1}{1}\left(1+\frac{1}{2}\left(1+\frac{1}{3}\left(1+\frac{1}{4}\left(\cdots \right)\right)\right)\right),\end{eqnarray} die man auch lesen kann als Darstellung von e im Stellenwertsystem zur variablen Basis \begin{eqnarray}b=(1;1/2,1/3,1/4,1/5,\ldots),\end{eqnarray} nämlich \(e=1.{\overline{1}}_{b}\). Ein Tröpfelalgorithmus für e gemäß Arthur H. J. Sale (1968) besteht aus der Umwandlung aus dem Stellenwertsystem zur Basis b ins Dezimalsystem.

Entsprechend leiteten im Jahr 1988 Daniel Saada und 1991 Stanley Rabinowitz aus der auf Leonhard Euler zurückgehenden, aus einer Reihenentwicklung des Arcustangens folgenden Formel \begin{eqnarray}\pi =2+2\displaystyle \sum _{n=1}^{\infty}\frac{1\cdot 2\cdot \cdots \cdot n}{3\cdot 5\cdot \cdots \cdot (2n+1)}\end{eqnarray} die Darstellung \begin{eqnarray}\pi =2+\frac{1}{3}\left(2+\frac{2}{5}\left(2+\frac{3}{7}\left(2+\frac{4}{9}\left(\cdots \right)\right)\right)\right)\end{eqnarray} von π im Stellenwertsystem zur variablen Basis \begin{eqnarray}b=(1;1/3,2/5,3/7,4/9,\ldots),\end{eqnarray} nämlich \(\pi =2.{\overline{2}}_{b}\), und damit einen Tröpfelalgorithmus für π ab.

Ein Vorteil solcher Tröpfelalgorithmen (neben ihrer Anschaulichkeit) ist, daß sie so implementiert werden können, daß nur Rechnungen mit kleinen ganzen Zahlen notwendig sind – beispielsweise reichen zur Berechnung von 15000 Stellen von π die gängigen 32-Bit-Ganzzahlen. Das Verfahren hat zwar einen Zeitbedarf von quadratischer Ordnung (d.h., zur Berechnung von n Dezimalstellen benötigt man proportional zu n2 viele Schritte) und damit nicht die Leistungsfähigkeit der Borwein-Iterationsverfahren oder des Brent-Salamin-Algorithmus, ist aber schneller als Algorithmen, die auf Arcustangensreihen für n beruhen.

Auch bei einem Tröpfelalgorithmus muß man jedoch im Voraus wissen, wieviele Stellen man berechnen will, und benötigt (im Gegensatz zur Ziffernextraktion) Speicherplatz einer Größe proportional zur Anzahl berechneter Stellen.

[1] Arndt, J.; Haenel, Ch.: Pi. Algorithmen, Computer, Arithmetik. Springer Berlin, 2000.
[2] Delahaye, Jean-Paul: Pi – Die Story. Birkhäuser Basel, 1999.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos