Die Bailey–Borwein–Plouffe-Formel, die es ermöglicht, jede bestimmte hexadezimale oder binäre Ziffer der Zahl Pi zu extrahieren, ohne vorherige Berechnungen durchzuführen (der aktuelle Rekord wurde mit dem Chudnovsky-Algorithmus aufgestellt, siehe unter dem Artikel).
Der Google Compute Engine-Berechnungscluster hat in 121 Tagen auf 25 virtuellen Maschinen die größte Anzahl an Ziffern der Zahl Pi berechnet und einen neuen Weltrekord aufgestellt: 31,4 Billionen Ziffern nach dem Komma. Dies ist das erste Mal, dass für die Berechnung einer so großen Zahl öffentliche Cloud-Software verwendet wurde.
Der Rekord wird auf den Namen von Emma Haruka Iwao aus der Abteilung für Hochleistungsrechnen bei Google eingetragen. Sie hat die Infrastruktur von Google Cloud für die Berechnungen genutzt. Der vorherige Weltrekord wurde 2016 von Peter Tschmuck mit 22,4 Billionen Ziffern aufgestellt. , der ebenfalls vom Arbeitgeber gesponsert wurde.
Wie Tschmuck verwendete die Google-Ingenieurin für die Berechnung y-cruncher. Dieses Programm nutzt , einen schnellen Algorithmus zur Berechnung der Zahl Pi. Schon in den 80er Jahren haben die damit eine Milliarde Ziffern nach dem Komma berechnet.
Der Algorithmus basiert wiederum auf der Eigenschaft der schnellen Konvergenz von hypergeometrischen Reihen:
Emma Haruka Iwao wurde von der "magischen" Zahl fasziniert, als sie in der Schule im Matheunterricht davon hörte. WiredAn der Universität war einer ihrer Professoren, Daisuke Takahashi, der Rekordhalter für die höchste Anzahl an berechneten Ziffern mit einem Supercomputer. Heute kann eigentlich jeder interessierte Ingenieur einen Rekord aufstellen, der Zugang zu ernsthaften Rechenressourcen und viel Speicherplatz (zur Speicherung der Berechnungsergebnisse) hat. Das 2009 entwickelte Programm ist zur Berechnung mathematischer Konstanten wie Pi gedacht. Es unterstützt massive Multithreading und Billionen von Berechnungsbereichen. Dieses Programm hat tatsächlich die Berechnung von Konstanten commodifiziert.
„Um den Weltrekord zu brechen, benötigt man einen ziemlich großen Computer“, sagt Ivao. „Es ist nicht möglich, dies mit einem handelsüblichen Computer zu machen, deshalb haben die Leute früher maßgeschneiderte Maschinen gebaut.“ Im September 2018 begann Ivao, sich zu überlegen, wie der Berechnungsprozess technisch funktionieren würde, um den Rekordbereich zu übertreffen. Sofort wurde klar, dass das Hauptproblem das Datenvolumen zum Speichern sein würde. Letztlich stellte sich heraus, dass das berechnete Ergebnis 170 Terabyte umfasst. Anstelle eines maßgeschneiderten Servers wie ihre Vorgänger verwendete sie die Infrastruktur von Google Cloud.
Ivao startete 25 virtuelle Maschinen: „Aber anstatt diese Schaltfläche für die virtuelle Maschine 25 Mal zu drücken, habe ich sie automatisiert“, erklärt sie. „Man kann das in ein paar Minuten erledigen, aber wenn man so viele Computer braucht, dauert es mehrere Tage, alles einzurichten.“ Dann überwachte Ivao kontinuierlich 121 Tage lang die Ausführung von y-cruncher auf diesen 25 virtuellen Maschinen.
Um die Berechnungen korrekt durchzuführen, mussten die virtuellen Maschinen ständig laufen. Die Ingenieurin richtete ein Überwachungssystem ein, das sie warnen würde, falls etwas schiefging, beispielsweise bei einem unerwarteten Ausfall einer der virtuellen Maschinen. Nur ein Ausfall – selbst für ein paar Minuten – hätte den gesamten Berechnungsprozess gefährden können, hätte sie nicht ein Backup.
„Im Cruncher und bei Google Cloud gibt es Backupsysteme, und ich habe sie so konfiguriert, dass man diese Festplatten sofort sichern kann, ohne die Berechnungen zu stoppen“, sagt Ivao. Diese Daten wurden dann kopiert und extern auf anderen Festplatten in Form von Momentaufnahmen gespeichert.
„Am Anfang gab es einige Parameter, die ich geändert habe, zum Beispiel, wie viele Daten man auf einmal lesen oder schreiben konnte und wie die Grenzen sich mit zunehmender Kapazität verschieben würden“, sagt Ivao.
Mit zunehmender Anzahl der Ziffern stieg das Volumen der Dateien, und die Komplexität der Berechnungen nahm nichtlinear zu. Dies erschwerte die ursprüngliche Berechnung erheblich, als Ivao versuchte zu bestimmen, welche Ressourcen der virtuellen Maschinen sie für das Projekt benötigen würde.
Jetzt sind sowohl die Berechnungen als auch die Ergebnisprüfung abgeschlossen: In y-cruncher sind zwei grundlegende Algorithmen integriert – einer zur Berechnung von Pi selbst und der andere zur Überprüfung. Der Prüfalgorithmus arbeitet parallel zur Berechnung, berechnet jedoch nur eine Ziffer, sodass der Rekord offiziell registriert werden kann.
Theoretisch könnte ein neuer Weltrekord aufgestellt werden, wenn man einfach die vorherige Datei nimmt und die Bailey-Borwein-Plouffe-Formel anwendet, um eine weitere Zahl zu berechnen. Aber das widerspricht sicherlich den Regeln zur Registrierung solcher Weltrekorde: Es ist sehr wahrscheinlich, dass jeder Anwärter die Berechnung von vorne beginnen muss. Alternativ: Das vorherige Ergebnis um N% verbessern, was mit der Bailey-Borwein-Plouffe-Formel nicht möglich ist.
Quelle: habr.com
