Svaret på livet, universet og alting
Et hold ledet af Andrew Sutherland fra MIT og Andrew Booker fra Bristol University har løst den sidste brik i et berømt 65 år gammelt matematisk puslespil med et svar på det mest flygtige tal af alle: 42.
Tallet 42 er især vigtigt for fans af science fiction-forfatteren Douglas Adams’ “The Hitchhiker’s Guide to the Galaxy”, fordi det er det tal, som en supercomputer har svaret på “det ultimative spørgsmål om livet, universet og alting”.
Booker ønskede også at kende svaret på 42. Det vil sige, er der tre terninger, hvis sum er 42?
Denne sum af tre terninger-puslespil, der første gang blev stillet i 1954 på University of Cambridge og er kendt som den diophantinske ligning x3+y3+z3=k, udfordrede matematikere til at finde løsninger for tallene 1-100. Med mindre tal er denne type ligning lettere at løse: f.eks. kan 29 skrives som 33 + 13 + 13, mens 32 er uløseligt. Alle blev til sidst løst, eller viste sig at være uløselige, ved hjælp af forskellige teknikker og supercomputere, undtagen for to tal:
Booker udtænkte en genial algoritme og brugte uger på sit universitets supercomputer, da han for nylig fandt en løsning på 33. Men da han skulle løse 42, fandt Booker ud af, at den nødvendige beregning var en størrelsesorden højere og måske oversteg hans supercomputeres kapacitet. Booker fortæller, at han fik mange tilbud om hjælp til at finde svaret, men i stedet henvendte han sig til sin ven Andrew “Drew” Sutherland, en ledende forsker i matematikafdelingen. “Han er verdens ekspert i den slags ting”, siger Booker.
Sutherland, hvis speciale omfatter massivt parallelle beregninger, slog i 2017 rekorden for den største Compute Engine-klynge med 580.000 kerner på Preemptible Virtual Machines, den største kendte højtydende computerklynge, der kører i den offentlige sky.
Som andre beregningsmæssige talteoretikere, der arbejder med aritmetisk geometri, var han bekendt med problemet med “summen af tre terninger”. Og de to havde tidligere arbejdet sammen og hjulpet med at opbygge L-functions and Modular Forms Database (LMFDB), et online atlas over matematiske objekter relateret til det, der er kendt som Langlands-programmet. “Jeg var begejstret, da Andy bad mig om at deltage i dette projekt”, siger Sutherland.
Booker og Sutherland drøftede den algoritmiske strategi, der skulle anvendes i søgningen efter en løsning på 42. Som Booker fandt ud af med sin løsning til 33, vidste de, at de ikke behøvede at prøve alle mulighederne for x, y og z.
“Der er en enkelt heltalsparameter, d, som bestemmer et relativt lille sæt af muligheder for x, y og z, således at den absolutte værdi af z er under en valgt søgegrænse B”, siger Sutherland. “Man opregner derefter værdier for d og kontrollerer hver af de mulige x, y, z, der er knyttet til d. I forsøget på at knække 33 var søgegrænsen B 1016, men denne B viste sig at være for lille til at knække 42; vi brugte i stedet B = 1017 (1017 er 100 millioner milliarder).”
Den væsentligste forskel mellem søgningen efter 33 og søgningen efter 42 ville ellers være størrelsen af søgningen og den anvendte computerplatform. Takket være et generøst tilbud fra det britiske Charity Engine var Booker og Sutherland i stand til at udnytte computerkraft fra over 400 000 frivilliges hjemme-pc’er over hele verden, som hver især fik tildelt en række værdier for d. Beregningen på hver pc kører i baggrunden, så ejeren stadig kan bruge sin pc til andre opgaver.
Sutherland er også fan af Douglas Adams, så projektet var uimodståeligt.
Metoden til at bruge Charity Engine minder om en del af handlingen omkring tallet 42 i romanen “Hitchhiker”: Efter at Deep Thought’s svar på 42 viser sig at være utilfredsstillende for forskerne, som ikke kender det spørgsmål, den skal besvare, beslutter supercomputeren at beregne det ultimative spørgsmål ved at bygge en supercomputer drevet af Jorden … med andre ord ved at anvende en verdensomspændende massivt parallel beregningsplatform.
“Dette er endnu en grund til, at jeg virkelig kunne lide at køre denne beregning på Charity Engine – vi brugte faktisk en computer i planetarisk skala til at afgøre et langvarigt åbent spørgsmål, hvis svar er 42.”
De kørte en række beregninger ved en lavere kapacitet for at teste både deres kode og Charity Engine-netværket. Derefter brugte de en række optimeringer og tilpasninger for at gøre koden bedre egnet til en massivt distribueret beregning sammenlignet med en beregning, der blev kørt på en enkelt supercomputer, siger Sutherland.
Hvorfor kunne Bristol’s supercomputer ikke løse dette problem?
“Tja, enhver computer *kan* løse problemet, hvis man er villig til at vente længe nok, men med omkring en halv million pc’er, der arbejder parallelt på problemet (hver med flere kerner), var vi i stand til at gennemføre beregningen meget hurtigere, end vi kunne have gjort ved hjælp af Bristol-maskinen (eller nogen af maskinerne her på MIT),” siger Sutherland.
Det er også mere energieffektivt at bruge Charity Engine-netværket. “For det meste bruger vi beregningsressourcer, som ellers ville gå til spilde,” siger Sutherland. “Når du sidder ved din computer og læser en e-mail eller arbejder på et regneark, bruger du kun en lille brøkdel af den disponible CPU-ressource, og Charity Engine-applikationen, som er baseret på Berkeley Open Infrastructure for Network Computing (BOINC), udnytter dette. Som følge heraf er CO2-fodaftrykket fra denne beregning – relateret til den elektricitet, som vores beregninger fik pc’erne i netværket til at bruge ud over, hvad de under alle omstændigheder ville have brugt – lavere, end det ville have været, hvis vi havde brugt en supercomputer.”
Sutherland og Booker kørte beregningerne over flere måneder, men den endelige vellykkede kørsel blev gennemført på blot et par uger. Da e-mailen fra Charity Engine kom, gav den den første løsning på x3+y3+z3+z3=42:
42 = (-80538738738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
“Da jeg hørte nyheden, var det helt sikkert et øjeblik med knytnæveslag,” siger Sutherland. “Med disse store beregninger bruger man en masse tid og energi på at optimere implementeringen, justere parametrene og derefter teste og teste koden igen og igen i løbet af uger og måneder, og man ved aldrig rigtig, om alle anstrengelserne vil betale sig, så det er ekstremt tilfredsstillende, når det gør det.”
Booker og Sutherland siger, at der er 10 tal mere, fra 101-1000, tilbage, der skal løses, og det næste tal er 114.
Men begge er mere interesserede i en enklere, men beregningsmæssigt mere udfordrende gåde: om der er flere svar på summen af tre terninger til 3.
“Der er fire meget lette løsninger, som matematikeren Louis J. Mordell, som i 1953 skrev berømt: “Jeg ved ikke noget om de heltalsløsninger af x3 + y3 + z3 + z3 = 3 ud over eksistensen af de fire tripler (1, 1, 1, 1), (4, 4, 4, -5), (4, -5, 4, 4), (-5, 4, 4, 4); og det må virkelig være meget vanskeligt at finde ud af noget om andre løsninger. Dette citat motiverede en stor del af interessen for summen af tre terninger problemet, og især tilfældet k=3. Selv om det formodes, at der burde være uendeligt mange løsninger, kender vi trods mere end 65 års søgen kun de nemme løsninger, som Mordell allerede kendte til. Det ville være meget spændende at finde en anden løsning for k=3.”