Die Bailey-Borwain-Plouffe-Formel, mit der Sie jede bestimmte hexadezimale oder binäre Ziffer von Pi extrahieren können, ohne die vorherigen zu berechnen (der aktuelle Datensatz wurde mit dem Chudnovsky-Algorithmus erstellt, siehe unten den Ausschnitt).
Der Rechencluster Google Compute Engine berechnete in 121 Tagen auf 25 virtuellen Maschinen die größte Anzahl an Ziffern in Pi und stellte damit einen neuen Weltrekord auf: 31,4 Billionen Dezimalstellen. Dies ist das erste Mal, dass öffentlich verfügbare Cloud-Software zur Berechnung von Pi in dieser Größenordnung verwendet wird.
Der Rekord wird im Namen von Emma Haruka Iwao von der High-Performance-Computing-Abteilung bei Google aufgenommen. Sie war es, die die Google Cloud-Infrastruktur für die Datenverarbeitung nutzte. Der bisherige Weltrekord wurde 2016 von Peter Troub aufgestellt, er errechnete die Zahl auf 22,4 Billionen Stellen , die ebenfalls vom Arbeitgeber gesponsert wurde.
Wie Trub nutzte der Google-Ingenieur Y-Cruncher für die Berechnung. Dieses Programm verwendet , ein schneller Algorithmus zur Berechnung von Pi. Damals in den 80ern es wurde verwendet, um eine Milliarde Dezimalstellen zu berechnen.
Der Algorithmus wiederum basiert auf der Eigenschaft der schnellen Konvergenz der hypergeometrischen Reihe:
Emma Haruka Iwao war von der „magischen“ Zahl fasziniert, nachdem sie im Mathematikunterricht in der Schule davon erfahren hatte. Kabelgebunden. An der Universität hielt einer ihrer Professoren, Daisuke Takahashi, den Rekord für die meisten Ziffern einer mit einem Supercomputer berechneten Zahl. Heutzutage kann der Rekord von fast jedem interessierten Ingenieur aufgestellt werden, der Zugang zu ernsthaften Rechenressourcen und großem Festplattenspeicher (zur Speicherung der Berechnungsergebnisse) hat. Programm erstellt im Jahr 2009 dient zur Berechnung mathematischer Konstanten wie Pi. Es unterstützt massive Multithreading- und Billionen-Skalierungsbereiche. Dieses Programm hat die Berechnung von Konstanten effektiv zur Ware gemacht.
„Man braucht einen ziemlich großen Computer, um den Weltrekord zu brechen“, sagt Iwao. „Man kann das nicht am Computer eines Ladens machen, deshalb haben die Leute früher maßgeschneiderte Autos gebaut.“ Im September 2018 begann Iwao darüber nachzudenken, wie der Berechnungsprozess über den Rekordbereich hinaus technisch funktionieren würde. Es war sofort klar, dass das Hauptproblem die Menge der zu speichernden Daten sein würde. Als Ergebnis stellte sich heraus, dass das berechnete Ergebnis 170 Terabyte benötigt. Anstatt wie ihre Vorgänger einen benutzerdefinierten Server zu erstellen, nutzte das Mädchen die Google Cloud-Infrastruktur.
Iwao nahm 25 virtuelle Maschinen in die Hand: „Aber anstatt den Knopf für die virtuelle Maschine 25 Mal zu drücken, habe ich ihn automatisiert“, erklärt sie. „Sie können es in ein paar Minuten erledigen, aber wenn Sie so viele Computer benötigen, wird es mehrere Tage dauern, bis alles eingerichtet ist.“ Anschließend ließ Iwao y-cruncher 121 Tage lang ununterbrochen auf diesen 25 virtuellen Maschinen laufen.
Damit die Berechnungen korrekt waren, mussten virtuelle Maschinen ständig laufen. Die Ingenieurin installierte ein Überwachungssystem, das sie warnte, wenn etwas schief ging, beispielsweise über einen plötzlichen Ausfall einer der virtuellen Maschinen. Nur ein einziger Ausfall – selbst für ein paar Minuten – könnte den gesamten Rechenprozess gefährden, wenn es kein Backup gäbe.
„Cruncher und Google Cloud verfügen über Backup-Systeme, und ich habe sie so eingerichtet, dass Sie sofort Kopien dieser Festplatten erstellen können, ohne die Berechnung anzuhalten“, sagt Iwao. Diese Daten wurden dann kopiert und als Snapshots extern auf anderen Laufwerken gespeichert.
„Am Anfang gab es ein paar Parameter, die ich geändert habe, etwa wie viele Daten man gleichzeitig lesen oder schreiben konnte und wie sich die Grenzen ändern würden, wenn man hineinzoomt“, sagt Iwao.
Mit zunehmender Ziffernzahl wurde das Dateivolumen größer und die Komplexität der Berechnungen nahm nichtlinear zu. Dies machte die anfängliche Berechnung sehr schwierig, als Iwao versuchte zu berechnen, wie viele virtuelle Maschinenressourcen sie für das Projekt benötigen würde.
Sowohl die Berechnungen als auch die Überprüfung des Ergebnisses sind nun abgeschlossen: In y-cruncher sind zwei grundlegende Algorithmen integriert – einer zur Berechnung von Pi selbst und der andere zur Überprüfung. Der Verifizierungsalgorithmus arbeitet parallel zur Berechnung, berechnet jedoch nur eine Ziffer, sodass der Datensatz offiziell registriert werden kann.
Theoretisch könnte ein neuer Weltrekord aufgestellt werden, indem man einfach die vorherige Datei nimmt und die Bailey-Borwain-Plouffe-Formel anwendet, um eine andere Zahl zu berechnen. Dies widerspricht jedoch wahrscheinlich den Regeln für die Registrierung solcher Weltrekorde: Höchstwahrscheinlich muss jeder Bewerber die Berechnung von vorne beginnen. Als Option: Verbesserung der bisherigen Leistung um N %, was nach der Bailey-Borwain-Plouffe-Formel nicht möglich ist.
Source: habr.com
