Formuła Bailey-Borweina-Pluffa pozwala na wyodrębnienie dowolnej konkretnej cyfry szesnastkowej lub binarnej liczby π bez obliczania wcześniejszych (aktualny rekord został ustalony za pomocą algorytmu Chudnovskiego, patrz niżej)
Klastr obliczeniowy Google Compute Engine w ciągu 121 dni na 25 maszynach wirtualnych obliczył największą liczbę cyfr liczby π, ustanawiając nowy światowy rekord: 31,4 biliona znaków po przecinku. To pierwszy raz, kiedy do obliczenia tak dużej liczby π wykorzystano oprogramowanie w chmurze dostępne dla ogółu społeczeństwa.
Rekord zostanie zapisany na nazwisko Emmy Haruki Iwao z działu obliczeń wysokowydajnych w Google. To ona wykorzystała infrastrukturę Google Cloud do obliczeń. Poprzedni światowy rekord został ustanowiony przez Petera Truba w 2016 roku, obliczył on liczbę do 22,4 biliona cyfr. , który także został sponsorowany przez pracodawcę.
Podobnie jak Trub, inżynier Google wykorzystała do obliczeń y-cruncher. Program ten wykorzystuje , szybki sposób obliczania liczby π. Już w latach 80. sama obliczyła miliard cyfr po przecinku przy jego pomocy.
Algorytm ten oparty jest na właściwości szybkiej zbieżności szeregów hipergeometrycznych:
Emma Haruka Iwao zainteresowała się «czarującą» liczbą, poznając ją podczas lekcji matematyki w szkole, Wired. Na uniwersytecie jeden z jej profesorów, Daisuke Takahashi, był rekordzistą w liczbie obliczonych cyfr liczby za pomocą superkomputera. Dzisiaj rekord może ustanowić praktycznie każdy zainteresowany inżynier, który ma dostęp do poważnych zasobów obliczeniowych i dużej przestrzeni dyskowej (do przechowywania wyników obliczeń). Stworzony w 2009 roku program jest przeznaczony do obliczenia stałych matematycznych, takich jak π. Obsługuje masową obsługę wielowątkową i zakresy w trylionach. Program ten faktycznie skomercjalizował obliczenia stałych.
„Potrzebujesz naprawdę dużego komputera, żeby pobić rekord świata – mówi Iwao. – Nie uda się tego zrobić na komputerze ze sklepu, dlatego dawniej ludzie budowali customowe maszyny“. We wrześniu 2018 roku Iwao zaczęła rozważać, jak technicznie będzie działał proces obliczeń w zakresie poza rekordowym. Od razu stało się jasne, że głównym problemem będzie ilość danych do przechowania. Ostatecznie okazało się, że obliczony wynik zajmuje 170 terabajtów. Zamiast budować customowy serwer, jak jej poprzednicy, dziewczyna użyła infrastruktury Google Cloud.
Iwao uruchomiła 25 maszyn wirtualnych: „Ale zamiast naciskać ten przycisk maszyny wirtualnej 25 razy, zautomatyzowałam to – wyjaśnia. – Możesz to zrobić w kilka minut, ale jeśli potrzebujesz tak wielu komputerów, to zajmie kilka dni, żeby wszystko skonfigurować“. Następnie nieprzerwanie przez 121 dni Iwao zarządzała działaniem y-cruncher na tych 25 maszynach wirtualnych.
Aby obliczenia były poprawne, maszyny wirtualne musiały działać bez przerwy. Inżynier zainstalowała system monitorowania, który ostrzegłby ją, jeśli coś poszłoby nie tak, na przykład o nagłym awarii jednej z maszyn wirtualnych. Tylko jedna awaria – nawet na kilka minut – mogła zagrozić całemu procesowi obliczeń, gdyby nie kopie zapasowe.
„W cruncherze i Google Cloud są systemy kopii zapasowych, a ja skonfigurowałam je tak, by można było natychmiast tworzyć kopie tych dysków, nie przerywając obliczeń – mówi Iwao. Te dane były następnie kopiowane i przechowywane zewnętrznie, na innych dyskach, w formie migawków.
„Na początku zmieniłam kilka parametrów, na przykład ile danych możesz odczytać lub napisać za jednym razem, oraz jak granice będą się zmieniać w miarę wzrostu”, mówi Iwao.
Wraz ze wzrostem liczby cyfr, objętość plików rosła, a złożoność obliczeń wzrastała nieliniowo. To bardzo skomplikowało początkowe obliczenia, gdy Iwao próbowała oszacować, jakich zasobów maszyn wirtualnych potrzebuje do projektu.
Obliczenia i weryfikacja wyniku zostały zakończone: w y-cruncher wbudowane są dwa podstawowe algorytmy - jeden do obliczania liczby pi, a drugi do weryfikacji. Algorytm weryfikacji działa równolegle do obliczeń, ale oblicza tylko jedną cyfrę, więc rekord można zarejestrować oficjalnie.
Teoretycznie, nowy światowy rekord można ustanowić, jeśli po prostu weźmiemy poprzedni plik i zastosujemy formułę Bailey'a - Borweina - Plouffa do obliczenia kolejnej liczby. Ale na pewno narusza to zasady rejestracji tego typu światowych rekordów: prawdopodobnie każdy pretendent musi zaczynać obliczenia od początku. Alternatywnie: poprawić poprzednie osiągnięcie o N%, co za pomocą formuły Bailey'a - Borweina - Plouffa nie będzie możliwe.
Źródło: habr.com
