Arndt • Haenel, 1t Springer-Verlag Berlin Heidelberg GmbH J örg Arndt • Christoph Haenel Pi Algorithmen, Computer, Arithmetik MitCD-ROM Zweite, überarbeitete und erweiterte Auflage i Springer Jörg Arndt Hühlweg 37 D-95448 Bayreuth Christoph Haenel Waldfriedenweg 24 D-82223 Eichenau ISBN 978-3-540-66258-7 Die Deutsche Bibliothek-CIP-Einheitsaufnahme [Pi]1t [Medienkombination]: Algorithmen, Computer, Arithmetik I Jörg Arndt; Christoph Haenel. ISBN 978-3-540-66258-7 ISBN 978-3-662-09360-3 (e Book) DOI 10.1007/978-3-662-09360-3 Buch.-2., überarb. und erw. Auf!. 2000 CD-ROM.-2., überarb. und erw. Auf!. 2000 Dieses Werk (Buch und CD-ROM) ist urheberrechtlich geschützt. Die dadurch begrün deten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielf:iltigung auf anderen Wegen und der Speicherung in Datenverarbeitungs anlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Verviel faltigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestim mungen des Urheberrechtsgesetzes. Additional material to this book can be downloaded from http://extra.springer.com. ©Springer-Verlag Berlin Heidelberg 1998,2000 Ursprünglich erschienen bei Springer-Verlag Berlin Heidelberg New York 2000 Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, daß solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Umschlaggestaltung: Künkel + Lopka Werbeagentur, Heidelberg Satz: Reproduktionsfertige Vorlage von den Autoren mit Springer TEX-Makros SPIN: 10721551 33/3142-543210 -Gedruckt auf säurefreiem Papier Nil desparare (Nicht verzweifeln) Sinnspruch in Gauß' Mathematischem Tagebuch (1796-1814), in dem der Zusammenhang zwischen 1r-Berechnung und arithmetisch-geometrischem Mittel aufgezeigt wird. Vorwort zur zweiten Auflage Nachdem die erste Auflage unseres Buchs über die faszinierende Zahl1r so gut angekommen ist, können wir jetzt die zweite Auflage präsen tieren, die wir völlig überarbeitet haben. Alle Themenbereiche sind erweitert, verbessert und auf den letzten Stand gebracht worden. Wir danken unseren Leserinnen und Lesern, indem wir ihre Anregungen eingefügt haben. Natürlich wird der neueste Weltrekord des japanischen Professors Kanada mit 68.7 Milliarden 1r-Stellen vermeldet und auch der Rekord des erst 17jährigen Colin Percival, der die 40billionste binäre 1r-Stelle mittels Internet-Kooperation berechnet hat (beides Anfang 1999). Da zu finden Sie z.B. jetzt die für moderne 1r-Berechnungen unerläßliche FFT-Multiplikation (Multiplikation mittels schneller Fourier-Transfor mation) ausführlich erklärt und mit Beispiel-Code unterlegt. Der historische Teil wurde völlig überarbeitet und erheblich ver größert. Auch haben wir die (plattformunabhängige) CD-ROM ausgeweitet; insbesondere haben wir 400 Millionen Dezimalstellen von 1r und die neuesten freeware Langzahl-Bibliotheken draufgepackt. Last but not least sind die WWW-Adressen zu den vielen 1r-Sites im Internet auf den letzten Stand gebracht. Zu besonderem Dank sind wir Herrn Prof. F.L. Bauer, TU München, verpflichtet. Er hat uns wertvollste Impulse und Verbesserungsideen zu allen Themen des Buchs gegeben. Wir sind stolz, von diesem Manne Förderung und Ratschlag erhalten zu haben. Auf die Resonanz und das Urteil unserer Leserinnen und Leser sind wir sehr gespannt. Für Ihre Kommentare haben wir eine eigene E-Mail Adresse eingerichtet; sie lautet pibook<Qj j j . de. Viel Vergnügen! Juni 1999 Jörg Arndt, Christoph Haenel Vorwort zur ersten Auflage Die Zahl 1r, von der die meisten nur wissen, daß sie das Verhältnis von Kreisumfang zu Kreisdurchmesser ausdrückt und mit 3.14 ... be ginnt, wurde im Juli 1997 auf 51.5 Milliarden Dezimalstellen genau berechnet. Was der Sinn solcher aberwitzigen Weltrekordberechnun gen ist und daß dabei jenseits der Ziffernfolge, die Tausende von Te lefonbüchern füllen würde, sehr viel mehr herauskommt, erfahren Sie in diesem Buch. Die Verfahren, die zu den hochgerrauen Berechnungen eingesetzt werden, spiegeln Ergebnisse der Mathematik wider, deren Bedeutung weit über das schiere "1r-Ausrechnen" hinausgeht. Diese neuen und effektiven Algorithmen haben überraschenderweise die an genehme Eigenschaft, leicht verständlich zu sein. Wir beschreiben die Einzelheiten der Rekordjagd und geben Ihnen auf der beigefügten CD-ROM Programme in die Hand, mit denen Sie auf Ihrem Computer selbst einige Millionen Stellen von 1r berechnen können. Alle Programme und Beispiele finden Sie auch im Source code, darüber hinaus auch weiterführende Texte zu Themen, die den Rahmen dieses Buches sprengen würden. Damit Sie eigene Recherchen im Internet starten können, haben wir auch an eine Sammlung von WWW-Links gedacht. Für die Statistiker unter Ihnen haben wir einige Millionen Stellen von 1r auf der CD-ROM untergebracht. Schließlich berichten wir auch von Personen und Begebenheiten der Historie von 1r, in der es neben Wissenschaftlichem auch einiges an Kuriosem und Verrücktem zu verzeichnen gibt. Bei der Entstehung dieses Buches haben uns die folgenden Perso nen mit Kommentaren und Anregungen sehr geholfen: Dieter Beule, Lothar Krüger, Heinz Pöhlmann, Georg Seßler, Mikko Tommila, Ute Zwerschke und auch ein besonders kooperativer Leser, der nicht ge nannt werden will. Ihnen allen sei an dieser Stelle ganz herzlich ge dankt! Wir wünschen Ihnen eine angenehme Reise in die faszinierende Welt der Zahl1r! Jörg Arndt, Christoph Haenel Inhaltsverzeichnis 1. Der Stand der Dinge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Wie zufällig ist 21 1r? . . . . . • . . • . • . . . . . . . . . . • • . • . . . . • . . . • 2.1 Wahrscheinlichkeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Ist 1r normal? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Doch nicht normal? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4 Das 163-Phänomen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.5 Weitere statistische Ergebnisse...................... 29 2.6 Die Intuitionisten und 1r • • • • • • • • • • • • • • • • • • • • • • • • • • • 30 2. 7 Kettenbruchdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3. Leichte Wege zu 35 1r • • • • • • . • . . • • . . . . . . . . . . . . . . . . . . . . . . 3.1 Kannitverstahn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 In der Kürze liegt die Würze . . . . . . . . . . . . . . . . . . . . . . . 37 3.3 1r und der Zufall (Monte-Carlo-Verfahren) . . . . . . . . . . . . 38 3.4 Memorabilia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.5 Bit für Bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.6 Verbesserungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.7 Der 1r-Saal in Paris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4. Näherungen für und Kettenbrüche. . . . . . . . . . . . . . . . 51 1r 4.1 Rationale Näherungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Andere Näherungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.3 Jugend nähert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4 Über Kettenbrüche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5. Arcus Tangens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.1 Die arctan-Formel von John Machin . . . . . . . . . . . . . . . . . 69 5.2 Weitere arctan-Formeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 X Inhaltsverzeichnis 6. Tröpfel-Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.1 Der Tröpfel-Algorithmus im Detail . . . . . . . . . . . . . . . . . . 78 6.2 Ablauf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.3 Eine schnellere Variante.. . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.4 Tröpfel-Algorithmus für e . . . . . . . . . . . . . . . . . . . . . . . . . . 85 7. Gauß und 1r......................................... 87 7.1 Die 1r-AGM-Formel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 7.2 Der GauB-AGM-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 90 7.3 Historie einer Formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 8. Ramanujan und 101 1r. • • . . • . . . . . . • . . . . . . . . . . . . . . . . . • . . . . 8.1 Ramanujansche Reihen ............................ 101 8.2 Ramanujans ungewöhnliche Biographie . . . . . . . . . . . . . . 104 8.3 Impulse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 9. Die Borweins und 1r ................................. 111 10. Das BBP-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 10.1 Binäre modulo-Exponentiation ...................... 120 10.2 Ein C-Programm zur BBP-Reihe . . . . . . . . . . . . . . . . . . . . 123 10.3 Verbesserungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 11. Arithmetik .......................................... 131 11.1 Multiplikation .................................... 131 11.2 Karatsuba-Multiplikation .......................... 132 11.3 FFT-Multiplikation ................................ 135 11.4 Division .......................................... 144 11.5 Quadratwurzel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 11.6 n-te Wurzel ...................................... 147 11.7 Reihen-Berechnung ................................ 148 12. Vermischtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 12.1 Ein Pi-Quiz ...................................... 151 12.2 Laßt Zahlen sprechen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 12.3 Ein Beweis für 1r = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 12.4 The Big Change .................................. 153 12.5 Fast voll daneben . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 12.6 Warum immer mehr Stellen? ....................... 156 12.7 Kreisquadratur mit Löchern . . . . . . . . . . . . . . . . . . . . . . . . 156 Inhaltsverzeichnis XI 13. Die Historie von 1r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 13.1 Altertum ......................................... 160 13.2 Polygone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 13.3 Unendliche Reihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 13.4 Hochleistungsalgorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . 190 13.5 Die Jagd nach Einzelstellen ......................... 195 Tabelle: Historie von bis zum 20. Jahrhundert ........... 197 1r Tabelle: Historie von im 20. Jahrhundert ............... 198 1r 14. Historische Notizen ................................. 199 14.1 Die früheste Kreisquadratur der Geschichte? .......... 199 14.2 Ein 1r-Gesetz ..................................... 201 14.3 Der Fall Hieberbach ............................... 203 15. Die Zukunft: 1r-Berechnungen im Internet . . . . . . . . . . 205 15.1 Der binsplit-Algorithmus ........................... 205 15.2 Das 1r-Projekt im Internet .......................... 209 16. Formelsammlung 1r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 17. Tabellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 17.1 Ausgewählte Konstante auf 100 Stellen (Basis 10) ..... 227 17.2 Die Stellen 0 bis 2 500 von (Basis 10) .............. 228 1r 17.3 Die Stellen 2 501 bis 5 000 von (Basis 10) ........... 229 1r 17.4 Die Stellen 0 bis 2 500 von (Basis 16) .............. 230 1r 17.5 Die Stellen 2 501 bis 5 000 (Basis 16) ............... 231 1r 17.6 Die Kettenbruch-Elemente 0 bis 1000 von 1r .•.....••• 232 17.7 Die Kettenbruch-Elemente 1001 bis 2 000 von 1r • •••••• 233 A. Documentation for the hfloat-library ................. 235 A.1 What hfloat is (good for) ........................... 235 A.2 Compiling the library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 A.3 Functions of the hfloat-library ....................... 236 A.4 Using hfioats in your own code ...................... 238 A.5 Computations with extreme precision ................ 241 A.6 Precision and radix ................................ 242 A.7 Compiling & running the 1r-example-code ............ 243 A.8 Structure of hfloat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 A.9 Organisation of the files ............................ 245 A.10 Distribution policy & no warranty .................. 246