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...= Du erkennst die Folge der Ziffern; und die Brüche 1/10 auf jeder Stufe sind die sogenannte arithmetische Basis, das ist die Folge a=(1/10, 1/10, 1/10,...)." "Ach so. Das ist wie das Horner-Schema zur Berechnung von Polynomen." "Stimmt. Es ist nicht gerade die übliche Art der Dezimaldarstellung, aber für unseren Zweck bequemer. Man kann auch andere Basen benutzen statt dieser, insbesondere gemischte Basen, das heißt, die Glieder der Basisfolge sind verschieden. Eine sehr nützliche Basis ist b=(1/2, 1/3, 1/4, 1/5,...). In dieser Basis ist eine gegebene Folge so zu verstehen: oder auch "Toll. Aber was soll das?" "Nun, bezüglich einer gemischten Basis haben bestimmte irrationale Zahlen sehr einfache Darstellungen. Zum Beispiel schreibt sich die Zahl e bezüglich der Basis b als 2,11111... . Denn es gilt die Gleichung "Langsam dämmert's mir", sagte Manfred. "Es geht lediglich darum, von der Darstellung zur Basis b in die zur Basis 10 – nein, Verzeihung, zur Basis (1/10, 1/10, 1/10,...) – umzurechnen. Die Lösung des Problems ist trivial bezüglich der Basis b, und der Tröpfel-Algorithmus vollführt gerade diesen Basiswechsel." "Eben. Es bleibt nur eine wesentliche Schwierigkeit: die Eindeutigkeit der Darstellung bezüglich der gemischten Basis. Wenn es für eine Zahl mehrere zulässige Dastellungen gibt, muß man aufpassen. Bei einer konstanten Basis ist es einfach; zum Beispiel muß bei der Basis (1/10, 1/10, 1/10,...) jeder Wert von zwischen 0 und 9 liegen. Und selbst dann hat man die Eindeutigkeit nicht so ganz exakt, denn 0,99999...=1,00000... ." "Ich denke, 0,99999... ist ein bißchen kleiner als 1." "Nur wenn man die Folge irgendwo abbricht. Es ist dasselbe, wenn man sie unendlich weiterlaufen läßt." "Ach!" "In der Basis b ist eine Darstellung eindeutig, wenn für jedes m gilt. Wenn man sich nun die Umrechnung in die Zehnerbasis überlegt, kommt man automatisch auf den Tröpfel-Algorithmus von Sale für e." Der Tröpfel-Algorithmus für e Es seien n Dezimalstellen zu berechnen. (1) Schreibe e als 2,111111... in der Basis b. Das gibt n+1 Einsen in der ersten Zeile. (2) Wiederhole nun (n+1)-mal folgende Operationen: (2.1) Multipliziere jedes Glied der vorliegenden Kette mit 10. (2.2) Beginnend von rechts dividiere das m-te Glied durch m+1. (2.3) Übertrage den Quotienten eine Stelle weiter nach links und addiere ihn zum dort stehenden Glied; den Rest notiere eine Zeile weiter unten. (2.4) Der letzte Übertrag (aus der ersten Spalte) ist die nächste Stelle von e. Ich erläuterte: "Schritt (2.2) entspricht der Operation ,dividiere durch Spalte B' und Schritt (2.3) der Operation ,multipliziere den Quotienten mit Spalte A'. Aber hier besteht Spalte A nur aus Einsen, weshalb es nichts zu multiplizieren gibt" (Bild 9). "Und das gibt e auf n Stellen?" "Das ergibt die ersten n Stellen von e. Es könnte sein, daß man die letzte Stelle eigentlich aufrunden müßte; deswegen ist es ratsam, n etwas größer zu wählen." "Ich glaube, das habe ich verstanden", meinte Manfred. "Bezüglich der Basis 10 erhält man die nächste Stelle einer Zahl, indem man den ganzzahligen Anteil abspaltet und das, was übrigbleibt, mit 10 multipliziert. Bezüglich der Basis b macht man es im Prinzip genauso, nur muß man hier noch mit zusätzlichen Schritten die Zahlen wieder in eine Form bringen, die der Bedingung für die eindeutige Darstellung genügt. Nur dafür braucht man alle diese Reste und Quotienten." "Ganz genau." Manfred dachte ein wenig nach. "Tröpfel-Algorithmus ist eigentlich ein alberner Name. Das ist doch eine Tabellenkalkulation." "Stimmt. Man könnte ihn ohne weiteres auch mit einem Tabellenkalkulationsprogramm umsetzen." Weiteres Nachdenken. "Geht das auch mit anderen Zahlen?" "Ja. Wenn du bei der Basis b bleiben willst, ist die Zahl zu empfehlen. Die erste Zeile ist 1 1 0 1 0 1 0 1 0 1 0 Dabei ist die vorderste Eins die erste Stelle der Lösung und der Rest die erste Zeile des Algorithmus" (Bild 10).

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, "Ich glaube dir jedes Wort." "Gut. Beachte, daß die Glieder der Basis c Brüche sind, deren Zähler und Nenner gerade in den Zeilen A und B des Tröpfel-Algorithmus stehen. Leider gibt es ein kleines Problem mit c. Die natürliche Bedingung für die Ziffern wäre . Die ist aber leider nicht ganz hinreichend für die Eindeutigkeit der Darstellung. Dieses Problem umgeht man am besten dadurch, daß man für manche Ziffern nur vorläufige Werte berechnet und diese später bei Bedarf nachbessert." Der Tröpfel-Algorithmus von Stanley Rabinowitz für die ersten n Stellen von PI (1) Der Algorithmus arbeitet auf einer Kette von [10n/3] ganzen Zahlen. Die eckigen Klammern bedeuten Runden nach unten auf die nächste ganze Zahl. Zu Beginn setze jedes Glied der Kette auf den Wert 2. (2) Wiederhole folgende Schritte n-mal: (2.1) Multipliziere jedes Glied mit 10. (2.2) Von rechts nach links führe mit jedem Glied folgende Schritte aus (die Spaltennummer m läuft also von n abwärts bis 2): (2.2.1) Berechne den Rest r und den Quotienten q bei der Division des m-ten Gliedes durch 2m-1. Ersetze das m-te Glied durch r. (2.2.2) Multipliziere q mit m-1 und addiere das Ergebnis (den Übertrag) zum (m-1)-ten Glied. (2.3) Das am weitesten links stehende Kettenglied kann Werte bis zu 109 annehmen. Es erhält eine Sonderbehandlung: Dividiere es durch 10 und ersetze es durch den Rest der Division; der Quotient Q ist die neue vorläufige Stelle von PI. (2.4) Wenn Q weder gleich 9 noch gleich 10 ist, erkläre alle bislang vorläufigen Stellen (mit Ausnahme von Q selbst) für endgültig. (2.5) Wenn Q=9 ist, füge es an die Liste der vorläufigen Stellen an. (2.6) Wenn Q=10 ist, erhöhe alle bislang vorläufigen Stellen um eins (aus 9 wird dabei 0) und erkläre sie für endgültig. Neue vorläufige Stelle ist 0 statt 10. Weitere Details zu diesem Verfahren findet man in dem unten zitierten Artikel von Rabinowitz und Wagon, der auch ein entsprechendes Pascal-Programm enthält. Mit dessen Hilfe läßt sich in wenigen Minuten PI bis auf 1000 Stellen genau berechnen. Manfred war offensichtlich beeindruckt und fragte ganz neugierig: "Kann man denn diesem Club noch beitreten?" "Aber natürlich. Nur, ganz so einfach ist es nicht. Du mußt als Einstand einen ideellen Beitrag leisten." "Was hast du denn beigetragen?" "Das war ein ganz obskures Integral zur Berechnung von ." "Ah ja." Er dachte ein Weile nach. "Gut. Ich hab's. Ich habe soeben einen Tröpfel-Algorithmus für alle Stellen von PI links vom Komma erfunden." "So schnell? Du mußt ein Genie sein. Und wie soll er funktionieren?" "Ganz einfach. Beginne mit 3. Multipliziere dann mit 0; das ergibt die vorhergehende Stelle. Wiederhole das beliebig oft." "Du bist aufgenommen", sagte ich auf der Stelle. "Tatsächlich? Für so einen grandiosen Unsinn?" "Du mußt wissen, der Verein ist extrem knapp bei Kasse. Es bleibt uns nichts übrig, als jeden zu nehmen, den wir kriegen können."

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