Bailey-Borwein-Plouffe-formlen, der gør det muligt at udtrække hvilken som helst specifik hexadecimale eller binære cifre af tallet pi uden at beregne de foregående (den nuværende rekord blev sat med Chudnovsky-algoritmen, se nedenfor)
Google Compute Engine beregningsklynge har på 121 dage med 25 virtuelle maskiner beregnet det største antal cifre i tallet pi, og har sat en ny verdensrekord: 31,4 trillioner decimaler. Dette er første gang, offentlig cloud-software blev anvendt til beregning af pi i så stor skala.
Rekorden vil blive registreret under navnet Emma Haruka Iwao fra Googles afdeling for højtydende beregninger. Det var hende, der brugte Google Clouds infrastruktur til beregningerne. Den tidligere verdensrekord blev sat af Peter Trueb i 2016, hvor han beregnede tallet til 22,4 trillioner cifre. , som også blev sponsoreret af arbejdsgiveren.
Ligesom Trueb anvendte Google-ingeniøren y-cruncher til beregningen. Dette program bruger , en hurtig algoritme til beregning af tallet pi. Allerede i 80'erne beregnede ved hjælp af det en milliard decimaler.
Algoritmen er i sin tur baseret på egenskaben af hurtig konvergens af den hypergeometriske rækkefølge:
Emma Haruka Iwao blev fascineret af det "magiske" tal, da hun lærte om det i matematikundervisningen i skolen, Wired. I universitetet var en af hendes professorer, Daisuke Takahashi, rekordinnehaver for antallet af beregnede cifre ved hjælp af en supercomputer. I dag kan næsten enhver interesseret ingeniør, som har adgang til betydelige beregningsressourcer og stor lagringsplads (til at gemme beregningsresultaterne), sætte rekorder. Programmet, der blev oprettet i 2009, er designet til at beregne matematiske konstanter som pi. Det understøtter massiv multithreading og trillioner af rækkevidder. Dette program har faktisk kommoditiseret beregningen af konstanter.
«Du har brug for en ret stor computer for at slå verdensrekorden,» siger Ivao. «Det kan ikke lade sig gøre med en butikcomputer, så tidligere byggede folk specialmaskiner.» I september 2018 begyndte Ivao at overveje, hvordan den tekniske beregningsproces ville fungere uden for rekordområdet. Det blev hurtigt klart, at den største udfordring ville være datamængden, der skulle opbevares. Resultatet viste sig at fylde 170 terabyte. I stedet for at samle en specialserver som sine forgængere brugte hun Googles Cloud-infrastruktur.
Ivao oprettede 25 virtuelle maskiner: «Men i stedet for at trykke på knappen for den virtuelle maskine 25 gange, automatiserede jeg det,» forklarer hun. «Du kan gøre det på et par minutter, men hvis du har brug for så mange computere, vil det tage flere dage at få det hele sat op.» Derefter styrede Ivao kontinuerligt y-cruncher på disse 25 virtuelle maskiner i 121 dage.
For at sikre beregningernes nøjagtighed skulle de virtuelle maskiner køre konstant. Ingeniøren installerede et overvågningssystem, der ville advare hende, hvis der skete noget, f.eks. et pludseligt nedbrud på en af de virtuelle maskiner. Bare én ulykke – selv i et par minutter – kunne true hele beregningsprocessen, hvis der ikke var en sikkerhedskopi.
«Kranchen og Google Cloud har backupsystemer, og jeg har konfigureret dem, så du kan tage øjebliksbilleder af disse diske uden at stoppe beregningerne,» siger Ivao. Disse data blev derefter kopieret og gemt eksternt på andre diske som snapshots.
«I starten var der flere parametre, som jeg ændrede, f.eks. hvor mange data du kunne læse eller skrive ad gangen, og hvordan grænserne ville ændre sig, når mængden steg,» siger Ivao.
Med det stigende antal cifre voksede filstørrelsen, og kompleksiteten af beregningerne steg nonlinear. Dette komplicerede den oprindelige beregning, da Ivao forsøgte at beregne, hvilken ressource kapacitet de virtuelle maskiner ville kræve til projektet.
Beregnings- og resultattjekket er nu afsluttet: y-cruncher har to grundlæggende algoritmer indbygget – en til at beregne selve pi, og en anden til at tjekke. Tjekalgoritmen arbejder parallelt med beregningen, men beregner kun ét ciffer, så rekorden kan registreres officielt.
Teoretisk set kan en ny verdensrekord sættes ved blot at tage den tidligere fil og anvende Bailey–Borwein–Plouffe-formlen til at beregne endnu et ciffer. Men det strider sikkert imod reglerne for registrering af sådanne verdensrekorder: sandsynligvis skal hver ansøger starte beregningen fra begyndelsen. En mulighed er at forbedre den tidligere præstation med N %, hvilket ikke kan gøres med Bailey–Borwein–Plouffe-formlen.
Kilde: habr.com
