Die Bailey–Borwein–Plouffe-Formel ermöglicht es, jede spezifische hexadezimale oder binäre Ziffer von Pi zu extrahieren, ohne die vorherigen zu berechnen (der aktuelle Rekord wurde mit dem Chudnovsky-Algorithmus aufgestellt, siehe unten).
Der Google Compute Engine Berechnungscluster hat in 121 Tagen auf 25 virtuellen Maschinen die größte Anzahl an Ziffern von Pi berechnet und einen neuen Weltrekord aufgestellt: 31,4 Billionen Ziffern nach dem Komma. Erstmals wurde für die Berechnung von Pi in dieser Größenordnung öffentliche Cloud-Software verwendet.
Der Rekord wird auf den Namen von Emma Haruka Iwao geschrieben, die im Bereich Hochleistungsrechnen bei Google arbeitet. Sie nutzte die Google Cloud Infrastruktur für die Berechnungen. Der vorherige Weltrekord wurde 2016 von Peter Trübenthal aufgestellt, der Pi bis zu 22,4 Billionen Ziffern berechnete. , welcher ebenfalls vom Arbeitgeber gesponsert wurde.
Wie Trüb, verwendete die Google-Ingenieurin zur Berechnung y-cruncher. Dieses Programm nutzt , einen schnellen Algorithmus zur Berechnung von Pi. Schon in den 80er Jahren selbst mit dessen Hilfe eine Milliarde Nachkommastellen berechnet wurden.
Der Algorithmus basiert seinerseits auf der Eigenschaft der schnellen Konvergenz der hypergeometrischen Reihe:
Emma Haruka Iwao wurde von der "magischen" Zahl fasziniert, als sie in der Schule im Matheunterricht darüber hörte, Wired. An der Universität war einer ihrer Professoren, Daisuke Takahashi, Rekordhalter für die meisten berechneten Ziffern dieser Zahl mithilfe eines Supercomputers. Heutzutage kann fast jeder interessierte Ingenieur, der Zugang zu ernsthaften Rechenressourcen und großem Speicherplatz hat (um die Berechnungsergebnisse zu speichern), einen Rekord aufstellen. Das 2009 entwickelte Programm ist zur Berechnung mathematischer Konstanten wie Pi vorgesehen. Es unterstützt massive Multithreading und Billionen von Bereichen. Dieses Programm hat die Berechnung von Konstanten tatsächlich commodifiziert.
„Um den Weltrekord zu brechen, benötigt man einen ziemlich großen Computer“, sagt Iwao. „Es ist nicht möglich, dies auf einem handelsüblichen Computer zu tun, weshalb Menschen früher maßgeschneiderte Maschinen bauten.“ Im September 2018 begann Iwao zu überlegen, wie der Rechnungsprozess technisch über den Rekordbereich hinaus funktionieren würde. Es war schnell klar, dass das Hauptproblem der Speicherbedarf sein würde. Am Ende ergab sich, dass das berechnete Ergebnis 170 Terabyte umfasst. Statt einen maßgeschneiderten Server wie ihre Vorgänger zusammenzustellen, nutzte das Mädchen die Infrastruktur von Google Cloud.
Iwao startete 25 virtuelle Maschinen: „Aber anstatt diesen Knopf für die virtuelle Maschine 25 Mal zu drücken, habe ich das automatisiert“, erklärt sie. „Du kannst das in wenigen Minuten erledigen, aber wenn du so viele Computer benötigst, dauert es mehrere Tage, alles einzurichten.“ Dann steuerte Iwao kontinuierlich für 121 Tage die Arbeit von y-cruncher auf diesen 25 virtuellen Maschinen.
Für die korrekte Durchführung der Berechnungen mussten die virtuellen Maschinen ständig laufen. Die Ingenieurin installierte ein Überwachungssystem, das sie benachrichtigen würde, wenn etwas schiefging, beispielsweise bei einem unerwarteten Ausfall einer der virtuellen Maschinen. Bereits ein Ausfall – selbst nur für ein paar Minuten – hätte den gesamten Berechnungsprozess gefährden können, wenn es nicht eine Sicherung gegeben hätte.
„In Cruncher und Google Cloud gibt es Backup-Systeme, und ich habe sie so konfiguriert, dass Sie diese Festplatten sofort sichern können, ohne die Berechnungen anzuhalten“, sagt Ivao. Diese Daten wurden dann extern auf anderen Festplatten als Schnappschüsse kopiert und gespeichert.
„Zu Beginn gab es einige Parameter, die ich geändert habe, wie beispielsweise, wie viele Daten Sie auf einmal lesen oder schreiben konnten und wie sich die Grenzen verändern werden, je mehr Daten verarbeitet werden“, erklärt Ivao.
Mit der Zunahme der Ziffern wuchs das Volumen der Dateien und die Komplexität der Berechnungen nahm nicht-linear zu. Dies erschwerte die ursprüngliche Berechnung erheblich, als Ivao versuchte zu berechnen, welche Ressourcen von virtuellen Maschinen sie für das Projekt benötigen würde.
Jetzt sind sowohl die Berechnungen als auch die Ergebnisüberprüfung abgeschlossen: y-cruncher beinhaltet zwei grundlegende Algorithmen – einen zur Berechnung von Pi und einen zur Überprüfung. Der Verifizierungsalgorithmus läuft parallel zur Berechnung, berechnet jedoch nur eine Ziffer, sodass der Rekord offiziell registriert werden kann.
Theoretisch könnte ein neuer Weltrekord aufgestellt werden, indem man einfach die vorherige Datei nimmt und die Bailey–Borwein–Plouffe-Formel anwendet, um eine weitere Ziffer zu berechnen. Dies widerspricht jedoch sicherlich den Regeln zur Registrierung solcher Weltrekorde: Jeder Antragsteller muss wahrscheinlich die Berechnungen von Grund auf neu beginnen. Alternativ könnte die vorherige Leistung um N % verbessert werden, was mit der Bailey–Borwein–Plouffe-Formel nicht möglich ist.
Quelle: habr.com
