Tröpfel-Algorithmen
Vielleicht genügt es Ihnen, die ersten paar tausend Stellen von PI zu berechnen. Hier ist ein extrem schnelles Verfahren für den Hausgebrauch.
Aber es gibt doch gar nichts Neues mehr über PI herauszufinden", sagte Manfred.
"Wirklich?" erwiderte ich. Eigentlich hatte sich Manfred nur eine Tüte Zucker ausleihen wollen. Aber ich war gerade auf dem Weg zur monatlichen Sitzung der Piosophischen Gesellschaft, kurz PISG, und hatte den – zugegeben – naiven Versuch unternommen, ihn aufzuklären und zu bekehren.
"Ich meine, nichts wirklich Interessantes. Schließlich kennt man die Kreiszahl auf Milliarden von Stellen hinter dem Komma. Wozu braucht man noch ein paar mehr?"
Ich wandte verzweifelt die Augen zum Himmel. "Mehr fällt dir dazu nicht ein? Meinst du, Mathematik bestehe darin, irgend etwas noch ein bißchen genauer auszurechnen?"
Da wurde er kleinlaut. "Natürlich nicht. Aber gerade PI. Das muß doch nun wirklich das abgegrasteste Gebiet der Mathematik sein."
Ich grinste. "Das, mein lieber Freund, liegt einfach daran, daß es eines der reichhaltigsten Gebiete ist. Erst vor sechs Jahren gab es große Neuigkeiten. Die Brüder Borwein haben eine erstaunliche neue Beziehung zu Ramanujans Theorie der Modulgleichungen entdeckt, die eine superkonvergente Näherung von PI liefert" (siehe "Srinivasa Ramanujan und die Zahl Pi" von Peter B. Borwein und Jonathan M. Borwein, Spektrum der Wissenschaft, April 1988, Seite 96).
"Superkonvergent?"
"Jeder Schritt des Verfahrens verfünffacht die Zahl der richtigen Dezimalstellen. Zum Beispiel."
"Und was macht man mit dieser umwerfenden Entdeckung?"
"Noch ein paar Dezimalstellen von PI berechnen", gab ich zu. "Na ja, ein paar Milliarden. Aber das war nur ein Test. Außerdem", fuhr ich hastig fort, "ist das überhaupt nicht einfach."
"Warum nicht?"
"Die üblichen Programmiersprachen arbeiten mit zehn Dezimalstellen – oder höchstens mit zwanzig bei doppelter Genauigkeit. Für sehr lange Ziffernfolgen muß man eine völlig andere Software benutzen."
Er nickte.
"Deshalb bin ich ja auch gespannt auf das heutige Thema." Manfred nahm die Tüte Zucker und schaute mich erwartungsvoll an.
"Und zwar?"
"Tröpfel-Algorithmen. Spigot algorithms auf englisch."
Er starrte mich an. "Ich verstehe nur Bahnhof."
"Paß auf. Ich zeige dir jetzt, wie man PI berechnet, eine Stelle nach der anderen und nur mit ganzzahliger Arithmetik", sagte ich. Auf einem Küchenpapier notierte ich drei schlichte Zahlenfolgen (Bild 1). "Das sind deine Startwerte. Jetzt folge meinen Anweisungen. Multipliziere jede Zahl in der letzten Zeile unter dem Strich mit 10."
"Überall 20, oder was? Das ist ja nicht schwer, aber es sieht noch nicht gerade wie PI aus."
"Noch nicht. Sei nicht so ungeduldig. Es kommen noch drei Zeilen darunter. Die oberste ist für den Übertrag, die mittlere für die Summe und die unterste für den Rest."
"Was denn? Addieren oder dividieren oder so?"
"Wart's ab. Man fängt am rechten Ende an, da ist der Übertrag 0" (Bild 2). "Dann addierst du den Übertrag zu der Zahl, die darüber steht, das ergibt 20. Jetzt kommt der trickreiche Teil. Was steht in Zeile B an der letzten Stelle über der Null?"
"Na ja – 25."
"Genau. Dividiere 20 durch 25. Was gibt das?"
"Vier Fünftel."
"Nein, ganzzahlige Arithmetik. Division mit Rest, wie in der Grundschule."
"Na schön. Wie oft ist 25 in 20 enthalten? Null mal, Rest 20."
"Richtig. Also r=20, q=0. Schreibe das r in die Zeile für den Rest. Dann multiplizierst du q mit der Zahl aus Zeile A, die ganz oben in der letzten Spalte steht, das ist?"
"12."
"Ja. Also hast du q=0 und 12 x 0 = 0. Das ergibt den nächsten Eintrag für die Zeile Übertrag."
Manfred hatte brav mitgeschrieben (Bild 3). Ich fuhr mit meinen Erklärungen fort: "Jetzt wiederholst du die ganze Prozedur eins weiter links. Also mußt du diesmal den Rest durch 23 dividieren, das ist die Zahl in Zeile B, die zur neuen Spalte gehört, und den Quotienten mit 11 malnehmen, der entsprechenden Zahl in Zeile A. Und der Übertrag steht noch eins weiter links" (Bild 4).
"Das ist aber nicht besonders spannend", meinte Manfred, nachdem er diesen und noch einen Schritt sorgsam ausgeführt hatte.
"Noch nicht. Du mußt noch etwas Geduld haben."
Tatsächlich ergab sich in den nächsten Schritten ein Übertrag, der nicht gleich null war (Bild 5). Aber die Rechnung war immer noch nicht sehr schwer, und bald war Manfred am linken Ende der Tabelle angelangt.
"Und jetzt? Es gibt nichts mehr, durch das ich teilen kann."
"Nimm die Summe 30 und fasse sie auf als einen Rest von 0 und einen Übertrag von 3, genauso wie du es im Dezimalsystem tun würdest. Schreibe die 0 in die Zeile für den Rest und die 3 auf ein neues Blatt Papier" (Bild 6).
"Na gut. Aber das ist doch albern."
"Eben nicht. Es ist soeben die erste Stelle von PI herausgetropft, nämlich 3."
"Was? Du meinst..."
"Ja, natürlich. Führe jetzt die gleichen Operationen nochmals aus, aber anstelle der Zweien nimmst du nun die Folge der Reste aus dem vorigen Durchgang. Dann erhältst du die nächste Stelle von PI, nämlich 1" (Bild 7).
"Und wieso Tröpfel-Algorithmus?"
"Weil die Dezimalstellen wie aus einem undichten Wasserhahn eine nach der anderen aus dem Apparat kommen und intern nicht wieder verwendet werden. Im Gegensatz dazu rechnet man bei einem klassischen Algorithmus ziemlich lange und ziemlich kompliziert, hat dann aber sogleich viele Stellen auf einmal."
Vielleicht möchten Sie den nächsten Durchgang selber ausprobieren. Zur Kontrolle zeigt Bild 8 das Ergebnis. In einem weiteren Durchgang müßte eine Eins herauströpfeln, so daß sich insgesamt 3,141 ergibt.
"Wie viele Stellen kann man so ausrechnen?", fragte Manfred.
"Nur die ersten vier", antwortete ich. "Aber wenn du n Stellen willst, mußt du einfach mit 3n+1 aufeinanderfolgenden Zweien anfangen. Du mußt die Zeilen A und B auf die naheliegende Weise fortführen und hast mehr Spalten zu bearbeiten, aber die Rechnungen sind einfache Operationen mit kleinen ganzen Zahlen. Und es wird nie besonders kompliziert."
Der Tröpfel-Algorithmus für e
"Ist denn das die übliche Methode?" fragte Manfred, jetzt deutlich interessierter. "Gab es da nicht einen Typ namens Ludolph van Ceulen, der vor ewig langer Zeit PI bis auf 20 Stellen genau berechnet haben soll?" "Ja, das stimmt, im Jahre 1596. Er lebte von 1540 bis 1610 und wirkte vor allem in Leiden. Lange Zeit hieß PI in Deutschland nur die Ludolphsche Zahl. Für die 20 Dezimalstellen hat er Jahre seines Lebens gebraucht; sie waren auf seinem Grabstein eingemeißelt, und er würde sich im Grabe umdrehen, wenn er wüßte, daß man das mit dem Tröpfel-Algorithmus in wenigen Stunden und mit 61 Spalten erledigen kann." Ich machte eine kleine Pause. "Es gibt noch einen zusätzlichen Dreh dabei, den ich dir noch nicht erzählt habe, aber den braucht man erst bei Berechnung der 32. Dezimalstelle." Manfred schüttelte verwundert den Kopf. "Und warum funktioniert das?" "Das ist eine besondere Geschichte", erwiderte ich. "Merkwürdigerweise wurde diese Methode erst 1968 von A. H. J. Sale entdeckt, und zwar zunächst nur für die Berechnung von e, der Basis der natürlichen Logarithmen. Die Erweiterung auf PI hat Stanley Rabinowitz aus Westford (Massachusetts) 1991 veröffentlicht. Er kam dank der Möglichkeiten moderner Rechner auf die Idee – zu einer Zeit, als man mit den Computern Ludolphs Verfahren bereits weiter getrieben hatte, als der sich je hätte träumen lassen. Es fängt mit der üblichen Dezimaldarstellung an. Daher rührt die Anweisung ,multipliziere alles mit 10'. Eine Dezimalzahl wie e=2,7182... kannst du auch als geschachtelten Klammerausdruck algebraisch darstellen: 2,7182...=
Zurück zur Kreiszahl
"Aber was ist mit PI?" fragte Manfred. "Aha, auf einmal interessierst du dich dafür. Ich dachte, es gäbe nichts Neues über PI zu erfahren." "Ich gebe zu, ich habe mich geirrt. Mach weiter." "Gut. Zuerst gilt es, eine Basis für die Darstellung von PI zu finden, auf die sich das Tröpfel-Verfahren anwenden läßt. Die Folge b scheint ungeeignet zu sein, denn dabei zeigt die Darstellung von PI keine schönen Regelmäßigkeiten. Aber man kann zeigen, daß bezüglich der Basis c=(1/3, 2/5, 3/7, 4/9, ...) die Darstellung PI=2,222222... gilt, das heißt,
Literaturhinweise
- Mathematical Recreations and Essays. Von W. W. Rouse Ball. MacMillan, New York 1959.
– Ramanujan, Modular Equations, and Approximations to Pi, or How to Compute One Billion Digits of Pi. Von J. M. Borwein, P. B. Borwein und D. H. Bailey in: American Mathematical Monthly, Band 96, Seiten 201 bis 219, 1989.
– A Spigot Algorithm for the Digits of PI. Von Stanley Rabinowitz und Stan Wagon in: American Mathematical Monthly, Band 102, Heft 3, Seiten 195 bis 203, 1995.
– The Calculation of e to Many Significant Digits. Von A. H. J. Sale in: Computing Journal, Band 11, Seiten 229 bis 230, 1968.
Aus: Spektrum der Wissenschaft 12 / 1995, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH
Schreiben Sie uns!
Beitrag schreiben