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