Direkt zum Inhalt

Eine Seilbahn für PI

In dem Sport, immer mehr Dezimalen der Kreiszahl zu finden, gibt es eine neue Disziplin: Man berechne eine Stelle von *, ohne sich um die davorliegenden zu kümmern.

Das Verhältnis von Umfang zu Durchmesser eines Kreises hatte Altmeister Archimedes (um 285 bis 212 vor Christus) auf einen Wert zwischen 310/71 und 31/7 eingegrenzt. Mit seinem Näherungsverfahren errechnete Ludolph van Ceulen (1540 bis 1610), Mathematiklehrer und Professor der Kriegsbaukunst in Leiden, zunächst 20, später 32 Dezimalen. Die Kreiszahl, später auch Ludolphsche Zahl genannt, erhielt von dem Schweizer Mathematiker Leonhard Euler (1707 bis 1783) ein eigenes Symbol: PI; und bis heute überbieten sich Genauigkeitsfanatiker darin, immer noch mehr Dezimalstellen der berühmten Zahl zu berechnen.

Etliche Gruppen haben sich gerade in den letzten Jahren wieder einen heftigen Wettstreit geliefert. Es handelt sich vor allem um Yasumasa Kanada und seine Mitarbeiter an der Universität Tokio sowie um Simon Plouffe und die Brüder Jonathan und Peter Borwein an der Simon-Fraser-Universität in Burnaby (British Columbia, Kanada). Zur Zeit hält Kanada mit reichlich sechs Milliarden Stellen hinter dem Komma den Rekord.

Das ganze Unternehmen ist wie Bergsteigen: äußerst mühsam und kräfte- beziehungsweise rechenzeitzehrend, weil jeder Ansturm in bislang unerreichte Höhen ganz unten anfangen muß. Um eine weitere Ziffer von PI zu berechnen, braucht man Informationen über alle vorhergehenden. Und einen unmittelbaren Nutzen gibt es ebensowenig wie im Alpinismus; für die meisten praktischen Zwecke ist Ludolphs Ergebnis mehr als ausreichend, und selbst extreme Genauigkeitsansprüche sind mit 100 Stellen mühelos zu befriedigen.

Warum macht man es also? Um der Größte zu sein – wenigstens auf diesem einen Gipfel. "Der Berg ruft", sagt der Extremkraxler, und das Hauptmotiv, das die Brüder Borwein in ihrem Artikel über PI (Spektrum der Wissenschaft, April 1988, Seite 96) anführen, ist von ähnlich entwaffnender Schlichtheit: "weil es Pi gibt".

Es gibt allerdings auch noch andere Gründe, die sich für einen Antrag auf Forschungsförderung etwas besser eignen. So ist die endlose Ziffernfolge ein interessantes Studienobjekt für Statistiker. Bislang ist sie mit deren Mitteln von einer Folge, in der die Ziffern 0 bis 9 mit jeweils gleicher Wahrscheinlichkeit ausgewürfelt werden, nicht zu unterscheiden (Bild). Andererseits gehorcht sie einer äußerst deterministischen Regel, und bislang ist nur empirisch belegt, aber nicht bewiesen, daß sie alle Eigenschaften einer Zufallsfolge hat. Da gibt es noch Verwendung für mehr Material zum Ausprobieren.

Außerdem ist die Berechnung dieser Ziffern eine ideale Testaufgabe für neue Computer und Programme. Jeder Rechenfehler pflegt bis ins Ergebnis durchzuschlagen; wenn also zwei verschiedene Systeme unabhängig voneinander dieselben Ziffern liefern, darf man mit Fug annehmen, daß beide einige Milliarden Rechenoperationen fehlerfrei durchgeführt haben. Durch einen derartigen Vergleich kam 1986 ein Hardware-Fehler in den ersten Supercomputern vom Typ Cray-2 ans Licht. Die Entdeckung eines Fehlers in den ersten Pentium-Chips ist auf eine ähnliche sportliche Anstrengung zurückzuführen: die Suche nach großen Primzahlen (Spektrum der Wissenschaft, Februar 1996, Seite 26).

Ein echter Bergsteiger sieht es normalerweise mit Mißvergnügen, wenn auf einem herausfordernden Berg eine Seilbahn installiert wird: Kommt er keuchend oben an, sitzen da schon Gondelladungen erholter Touristen über ihrer Brotzeit. Nun gibt es neuerdings eine Seilbahn für PI: Die Borweins und Simon Plouffe haben ein Verfahren gefunden, mit dem man eine beliebige Stelle hinter dem Komma berechnen kann, ohne die vorherigen kennen zu müssen. Aber von Mißvergnügen keine Spur – man staunt darüber, daß so etwas im Prinzip möglich ist; die Brüder Borwein selbst hatten es noch wenige Jahre zuvor für praktisch ausgeschlossen erklärt. Im übrigen stört es ja nicht wirklich, wenn Amateure mit ihren PCs jetzt einige Großleistungen nachvollziehen können. Jonathan und Peter Borwein stellen dafür sogar Literatur, einige Handhaben und weitere Verweise im Netz zur Verfügung (http://www.cecm.sfu.ca/personal/pborwein/).

Die Entdeckung kam nicht nur auf einem Gebiet, auf dem niemand mehr ernsthaft mit Neuigkeiten gerechnet hatte; sie verwendet auch ausschließlich Mittel, die seit 200 Jahren bereitliegen und so sehr Allgemeingut geworden sind, daß sie mancherorts zum Schulstoff gehören. Jemand wie Euler hätte ohne weiteres darauf kommen können.


Kreisberechnung nach Ägypterart

Das klassische Verfahren des Archimedes, bei dem der Kreisumfang durch ein- und umbeschriebene Vielecke angenähert wird, erfordert in jedem Iterationsschritt das Ziehen einer Wurzel. Das gilt auch für die völlig anders begründeten Verfahren, mit denen die PI-Ersteiger ihre jüngsten Rekorde aufstellten und die auf den Notizbüchern des indischen Autodidakten Srinivasa Ramanujan (1887 bis 1920) basieren (vergleiche den zitierten Artikel der Brüder Borwein). Mit modernen Methoden ist Wurzelziehen zwar nicht wesentlich aufwendiger als Multiplizieren; dennoch scheinen jene Vorgehensweisen besonders interessant, die ohne diese Operation auskommen. Das gilt auch für den Tröpfel-Algorithmus, der zwar für Bergsteiger, die hoch hinauswollen, ungeeignet ist, aber kleine und mittlere Ansprüche mit erstaunlich geringem Aufwand an Speicherplatz und Software befriedigt (Spektrum der Wissenschaft, Dezember 1995, Seite 10).

In diesem Zusammenhang ist bemerkenswert, daß es auch eine Methode der Kreisberechnung mit einbeschriebenen Vielecken gibt, die ein Minimum an Wurzeln benötigt: Außer SQRT2 und SQRT5 kommen nur rationale Zahlen vor. Franz Gnädinger aus Zürich hat sie gefunden (Kasten auf Seite 12).

Motiviert wurde er durch die Suche nach den mathematischen Fähigkeiten der antiken Ägypter. Das Verfahren des Archimedes hätte, wenn es ihnen denn in den Sinn gekommen wäre, ihre bescheidenen arithmetischen Fähigkeiten zweifellos überfordert. Gnädinger hält es jedoch für voreilig, ihnen deshalb zu unterstellen, sie hätten keine brauchbare Näherung an PI gehabt. Sein Verfahren ist geometrisch begründet und verwendet ausschließlich Kenntnisse, die damals verfügbar waren, insbesondere über pythagoräische rechtwinklige Dreiecke. Für die Wurzeln aus 2 und 5 gibt er ebenfalls geometrisch motivierte Approximationen an, die mit Fibonacci-Folgen arbeiten. Näheres findet man im WWW unter http://www.access.ch/circle.

Das Seilbahn-Verfahren

Wie funktioniert nun die neue Methode? In der klassischen Analysis führt der erste Berechnungsschritt von PI zu den Winkelfunktionen Sinus, Cosinus und Tangens. Man pflegt Winkel im Bogenmaß auszudrücken, das heißt als Verhältnis von zum Winkel gehörigem Kreisbogen und Kreisradius. Ein Winkel von 90 Grad entspricht PI/2, 45 Grad sind PI/4, und der Tangens von PI/4 ist 1 (nämlich gleich dem Verhältnis der Katheten im gleichschenklig-rechtwinkligen Dreieck). Man löse nun die Gleichung tan(PI/4)=1 nach PI auf, indem man auf beide Seiten die Umkehrfunktion des Tangens (den Arcustangens) anwendet, und erhält PI=4 arctan(1). Die Arcustangens-Funktion ist übrigens weniger exotisch, als ihr Name vermuten läßt; sie ist in jedem besseren Taschenrechner unter der Tastenfolge INV TAN eingebaut.

Weiter kommt man mit Hilfe der Differential- und Integralrechnung. Die Ableitung der Funktion arctan x ist 1/(1+x2). Das ist eine rationale Funktion, das heißt ein Bruch, dessen Zähler und Nenner Polynome – Funktionen der Form a0+a1x+a2x2+... anxn – sind. Mit Funktionen dieser Klasse läßt sich allerlei Bruchrechnung treiben; vor allem aber kann man 1/(1+x2) als Summe einer geometrischen Reihe mit dem Quotienten -x2 auffassen: 1/(1+x2) =1-x2+x4-x6+x8-...

Das ist schon alles. Mit Hilfe geläufiger Formeln aus den genannten Gebieten der Analysis kann man eine neue Summenformel für PI herleiten. Der Beweis ist nicht besonders tiefsinnig, allenfalls sehr lästig wegen der vielen algebraischen Umformungen (Kasten Seite 13); aber die sind inzwischen bequem mit einem Computeralgebra-Programm zu erledigen.

Wenn das alles so einfach ist, wieso ist dann in den letzten anderthalb Jahrhunderten niemand sonst auf die Idee gekommen? Nun, auch die Borweins und Plouffe haben die Formel nicht einfach aus dem Ärmel geschüttelt. Sie ergab sich im Verlauf einer systematischen Suche nach Beziehungen unter ganzen Zahlen mit Hilfe des Programms PLSQ, das von David Bailey vom Ames-Forschungszentrum der NASA in Moffett Field (Kalifornien) stammt. Auf demselbem Wege fanden die Forscher gleichartige Formeln für PI2, SQRT2 und einige weitere Konstanten.

Wie aber hilft einem diese merkwürdige Formel, an die millionste Stelle von PI zu kommen, ohne die anderen 999999 ausrechnen zu müssen? Stellen Sie sich vor, im Nenner vor der Klammer stünde nicht 16i, sondern 10i, und innerhalb der Klammer nicht eine Summe von vier Brüchen, sondern einfach eine ganze Zahl zwischen 0 und 9. Dann wäre das Problem erledigt, denn die Formel wäre nichts weiter als die Beschreibung einer Dezimalbruchdarstellung: 3,14159... = 3+1/101+4/102+1/103+5/104+9/105..., und die n-te Stelle wäre gleich dem n-ten Glied der Summe. Die Formel liefert also im Prinzip schon die Lösung – wenn diese beiden Schönheitsfehler nicht wären. Wie kann man sie beheben?

Eine praktikable Formel, in der 10 anstelle von 16 stünde, ist noch nicht bekannt. Plouffe hat im Dezember letzten Jahres eine solche Formel vorgeschlagen; der zugehörige Algorithmus benötigt zwar sehr wenig Speicherplatz, aber enorm viel Zeit. Hier sind die Dinge noch sehr im Fluß. Einstweilen müssen wir uns damit begnügen, die Seilbahn nur im Sechzehner-, nicht aber im Dezimalsystem betreiben zu können. Man darf eben nicht erwarten, daß eine universelle Konstante wie PI auf den Umstand Rücksicht nimmt, daß die Menschen zehn Finger haben und das heute geläufige Zahlensystem darauf gegründet ist.

Dem zweiten Schönheitsfehler hingegen ist abzuhelfen. Es sei die n-te Stelle hinter dem Komma in der Sechzehnerdarstellung von PI gesucht. Dann verschieben wir zunächst das Komma um n-1 Stellen nach rechts, so daß die gesuchte Ziffer unmittelbar rechts vom Komma steht. Das heißt, wir multiplizieren die ganze Formel mit 16n-1 und suchen in der entstehenden Zahl die erste Ziffer nach dem Komma. Es handelt sich um eine Summe von vier unendlichen Reihen; es genügt, sich exemplarisch die erste von ihnen anzusehen. Wie findet man also die erste Stelle hinter dem Komma von

((MUPiFormel.ps))

Die unendlich vielen Glieder der Summe werden zunehmend kleiner; wenige Glieder nach dem n-ten sind sie bereits so klein, daß sie auf die erste Stelle hinter dem Komma keinen Einfluß mehr haben können. Man darf sie also einfach vergessen.

Aber es sieht so aus, als müßte man für die ersten n Glieder (und das sind vielleicht eine Million) eine Potenz von 16 ausrechnen und durch 8k+1 dividieren. Das Angenehme ist: Man muß nicht. Man interessiert sich ja nicht für das, was vor dem Komma steht, sondern nur für den nicht-ganzzahligen Anteil. Ob man wirklich den Zähler des Bruches ausrechnet oder eine Zahl, die sich von diesem um ein Vielfaches von 8k+1 unterscheidet, ist völlig gleichgültig. Also rechnet man nicht mit den echten Zahlen, sondern modulo 8k+1: mit dem Rest, der jeweils bei Division durch diese Zahl übrigbleibt.

Da bei diesem Verfahren alle Zahlen von mäßiger Größenordnung bleiben, ist es vergleichsweise schnell (vergleiche Spektrum der Wissenschaft, September 1996, Seite 80). Am Ende sind für die millionste Stelle zwar vier Millionen Zahlen auszurechnen; aber es sind kleine Zahlen, und deswegen ist der Rechenaufwand unvergleichlich kleiner als der für die Berechnung aller Stellen bis zur millionsten.

Die Entdeckung des neuen Verfahrens ist ohne Zweifel überraschend, und die Begeisterung der Fachleute ist nachvollziehbar. Doch muß man eingestehen, daß PI-Steigen, mit oder ohne Seilbahn, in einigen Aspekten deutlich öder ist als Bergsteigen. Erstens gibt es keinen Gipfel. Die Ziffernfolge hört einfach nicht auf; sie kann nicht einmal periodisch werden – denn dann wäre PI rational, und das ist nachweislich nicht der Fall.

Zweitens ist die Aussicht von da oben, einerlei wie hoch man kommt, auch nicht besonders eindrucksvoll. Die Ziffernfolge ist nicht nur im Detail zufallsähnlich, sondern global gesehen von erdrückender Gleichförmigkeit. Abweichungen von der Gleichverteilung der Ziffern, Ziffernpaare und so weiter halten sich im Rahmen des statistisch zu Erwartenden. Man kann zum Beispiel mit großer Sicherheit davon ausgehen, daß man sein Geburtsdatum – oder irgendeine Folge von sechs Ziffern – in der Folge der ersten Milliarde Ziffern ungefähr eintausendmal wiederfindet.

Wer also trotz Seilbahn am Boden bleibt, hat ein intellektuelles Abenteuer verpaßt – aber sonst bestimmt nichts.

Literaturhinweise

- PI: A 2000-Year Search Changes Direction. Von Victor Adamchik und Stan Wagon in: Mathematica in Education and Research, Band 5, Heft 1, Seiten 11 bis 19, 1996.

– The Quest for Pi. Von David H. Bailey, Jonathan M. Borwein, Peter B. Borwein und Simon Plouffe. Preprint, 1996.

– Obsession de PI. Von Jean-Paul Delahaye in: Pour la Science, Januar 1997, Seiten 104 bis 108.

Kasten: Das Verfahren von Franz Gnädinger zur Berechung von PI

Wie bei Archimedes wird die Kreislinie durch (geradlinige) Sehnen zwischen ausgewählten Punkten approximiert. Im Verlauf des Verfahrens werden diese Punkte immer dichter gelegt, so daß der entstehende Streckenzug sich dem Kreis immer besser anschmiegt. Anders als Archimedes legt Gnädinger seine Stützpunkte nicht genau in die Mitte zwischen zwei bereits vorhandenen, sondern so, daß die Sehnenlängen besonders einfach zu berechnen sind. Jede Sehne ist Hypotenuse c eines rechtwinkligen Dreiecks, dessen beide anderen Seiten a und b parallel zu den Achsen eines Koordinatensystems verlaufen. Nach dem Satz des Pythagoras ist a2+b2=c2, nach c aufgelöst c=SQRT(a2+b2). Wurzeln zu berechnen ist mühsam, besonders mit den Mitteln der Antike. Gnädinger legt seine Punkte so, daß es genügt, die Wurzeln aus 2 und aus 5 zu berechnen. Sonst kommen nur rationale Zahlen vor. Hingegen ist in jedem Schritt des archimedischen Verfahrens eine Wurzel aus einer neuen Zahl zu ziehen. Der Schlüssel zu Gnädingers Verfahren ist das berühmte Dreieck mit den Seiten 3, 4 und 5. Es ist rechtwinklig, denn diese drei Zahlen bilden ein pythagoräisches Tripel: 32+42=52. Man zeichne in einen Kreis mit Radius 5 ein Gitternetz der Maschenweite 1 ein. Dann liegen – abgesehen von den Koordinatenachsen selbst – genau diejenigen Gitterpunkte auf der Kreislinie, zu denen es ein pythagoräisches Dreieck aus Gitterlinien gibt (a). Man verbinde diese Punkte durch Sehnen; diese sind Hypotenusen rechtwinkliger Dreiecke, deren Katheten auf Gitterlinien liegen (b). Im nächsten Schritt gilt es, weitere Punkte mit diesen angenehmen Eigenschaften zu finden. Dazu verfeinert man das Gitternetz um das Fünffache – oder vergrößert den Kreis entsprechend, was auf dasselbe hinausläuft – und findet weitere Gitterpunkte, die auf der Kreislinie liegen. Wenn man eines der ursprünglichen pythagoräischen Dreiecke um den Kreismittelpunkt dreht, bis eine Kathete auf die bisherige Hypotenuse zu liegen kommt, wandert seine äußerste Ecke auf der Kreislinie entlang und liegt schließlich in einem neuen Gitterpunkt. Die so vermehrten Stützpunkte ergeben schon eine bessere Approximation an die Kreislinie (c). Verfeinert man das Gitter nochmals mit dem Faktor 5, ergeben sich weitere Stützpunkte, und so weiter. Algebraisch läuft das Verfahren darauf hinaus, möglichst viele pythagoräische Tripel a, b, c zu finden, die das c gemeinsam haben. Man beginnt mit dem klassischen Tripel 3, 4, 5; multipliziert man sämtliche Werte mit 5, erhält man wieder ein pythagoräisches Tripel: 15, 20, 25. Es ist aber nicht nur 5a, 5b, 5c ein solches Tripel, sondern auch 4b-3a, 3b+4a, 5c, im Beispiel: 7, 24, 25. Nach dieser Formel vermehrt man in jedem Schritt die Anzahl der Tripel um 1. Indem man a und b vertauscht und nach Belieben mit Minuszeichen versieht oder auch nicht, gewinnt man aus jedem Tripel acht Stützpunkte. Aus den besonderen Eigenschaften des Tripels 3, 4, 5 und der Konstruktion ergibt sich, daß alle zu berechnenden Wurzeln fast glatt aufgehen. Es bleiben schlimmstenfalls Wurzeln aus 2, aus 5 und deren Produkt übrig. Das Verfahren konvergiert langsam, erfordert aber auch nicht allzu großen Rechenaufwand. Mit 41 Tripeln und 332 Stützpunkten (die vier auf den Koordinatenachsen mitgezählt) erhält man immerhin fünf korrekte Dezimalstellen von PI.

Kasten: Die Borweinsche Formel für PI

x


Aus: Spektrum der Wissenschaft 5 / 1997, Seite 10
© Spektrum der Wissenschaft Verlagsgesellschaft mbH

Kennen Sie schon …

51/2019

Spektrum - Die Woche – 51/2019

In dieser Ausgabe geht es under anderem um den Start des CHEOPS-Teleskops, den umstrittenen Rorschach-Test und den Frühmensch Homo erectus.

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!