Formula Bailey-Borwain-Plouffe, koja vam omogućava da izvučete bilo koju specifičnu heksadecimalnu ili binarnu cifru pi bez izračunavanja prethodnih (trenutni rekord je postavljen pomoću Chudnovsky algoritma, pogledajte ispod rezanja)
Računarski klaster Google Compute Engine izračunao je najveći broj cifara u pi u 121 dan na 25 virtuelnih mašina, postavivši novi svjetski rekord: 31,4 triliona decimalnih mjesta. Ovo je prvi put da je javno dostupan softver u oblaku korišten za izračunavanje pi ove veličine.
Rekord će biti snimljen na ime Emma Haruka Iwao iz odjela za računarstvo visokih performansi u Googleu. Upravo je ona koristila Google Cloud infrastrukturu za računarstvo. Prethodni svjetski rekord postavio je Peter Troub 2016. godine, izračunao je broj na 22,4 triliona cifara , koju je također sponzorirao poslodavac.
Kao i Trub, Google inženjer je koristio y-cruncher za proračun. Ovaj program koristi , brzi algoritam za izračunavanje pi. I sami u 80-im korišćen je za izračunavanje milijarde decimala.
Zauzvrat, algoritam se temelji na svojstvu brze konvergencije hipergeometrijskog niza:
Emma Haruka Iwao je postala fascinirana "magičnim" brojem nakon što je saznala za njega na času matematike u školi. Wired. Na univerzitetu, jedan od njenih profesora, Daisuke Takahashi, držao je rekord za najveći broj cifara izračunatih pomoću superkompjutera. Danas rekord može postaviti gotovo svaki zainteresovani inženjer koji ima pristup ozbiljnim računarskim resursima i velikim diskovima (za pohranjivanje rezultata proračuna). Program kreiran 2009 je dizajniran za izračunavanje matematičkih konstanti kao što je pi. Podržava masivne višenitne i trilijunske opsege. Ovaj program je efikasno komodizirao izračunavanje konstanti.
„Potreban vam je prilično veliki računar da biste oborili svetski rekord“, kaže Iwao. “Ne možete to učiniti na kompjuteru iz radnje, pa su ljudi nekada pravili automobile po narudžbi.” U septembru 2018. Iwao je počeo razmatrati kako bi proces izračunavanja tehnički funkcionirao izvan rekordnog raspona. Odmah je postalo jasno da će glavni problem biti količina podataka koji će se pohraniti. Kao rezultat toga, pokazalo se da izračunati rezultat traje 170 terabajta. Umjesto izrade prilagođenog servera, kao i njeni prethodnici, djevojka je koristila Google Cloud infrastrukturu.
Iwao je pokupio 25 virtuelnih mašina: „Ali umesto da pritisnem to dugme virtuelne mašine 25 puta, ja sam ga automatizovala“, objašnjava ona. "Možete to učiniti za nekoliko minuta, ali ako vam treba toliko računara, trebat će nekoliko dana da se sve podesi." Iwao je zatim pokrenuo y-cruncher na tih 121 virtuelnih mašina neprekidno 25 dan.
Da bi proračuni bili tačni, virtuelne mašine su morale da rade konstantno. Inženjer je instalirao sistem za praćenje koji bi je upozorio ako nešto krene po zlu, na primjer, o iznenadnom kvaru na jednoj od virtuelnih mašina. Samo jedan kvar - čak i na nekoliko minuta - mogao bi ugroziti cijeli proces računanja da nije rezervna kopija.
„Cruncher i Google Cloud imaju sisteme rezervnih kopija, a ja sam ih postavio tako da možete odmah uzeti kopije tih diskova bez zaustavljanja proračuna“, kaže Iwao. Ovi podaci su zatim kopirani i pohranjeni eksterno, na drugim diskovima, kao snimci.
“U početku sam promijenio nekoliko parametara, kao što je koliko podataka možete čitati ili pisati u jednom trenutku i kako će se granice mijenjati kako zumirate,” kaže Iwao.
Kako se broj cifara povećavao, volumen datoteka je postajao sve veći, a složenost proračuna se povećavala nelinearno. Ovo je otežalo početni proračun kada je Iwao pokušavala izračunati koliko će joj resursa virtuelne mašine biti potrebno za projekat.
Sada su i proračuni i verifikacija rezultata završeni: dva osnovna algoritma su ugrađena u y-cruncher - jedan za izračunavanje samog pi, a drugi za verifikaciju. Algoritam verifikacije radi paralelno sa proračunom, ali računa samo jednu cifru, tako da se zapis može zvanično registrovati.
U teoriji, novi svjetski rekord bi se mogao postaviti jednostavnim uzimanjem prethodne datoteke i primjenom formule Bailey-Borwain-Plouffea za izračunavanje drugog broja. Ali to je vjerovatno u suprotnosti s pravilima za registraciju takvih svjetskih rekorda: najvjerovatnije, svaki podnositelj zahtjeva mora započeti obračun iz početka. Kao opcija: poboljšati prethodno postignuće za N%, što se ne može učiniti prema Bailey-Borwain-Plouffe formuli.
izvor: www.habr.com
