Het antwoord op leven, het universum en alles
Een team onder leiding van Andrew Sutherland van het MIT en Andrew Booker van de Bristol University heeft het laatste stukje van een beroemde 65 jaar oude wiskundepuzzel opgelost met een antwoord op het meest ongrijpbare getal van allemaal: 42.
Het getal 42 is vooral van belang voor fans van sciencefiction romanschrijver Douglas Adams’ “The Hitchhiker’s Guide to the Galaxy,” omdat dat getal het antwoord is dat een supercomputer geeft op “de Ultieme Vraag van het Leven, het Universum, en Alles.”
Booker wilde ook het antwoord op 42 weten. Dat wil zeggen, zijn er drie kubussen waarvan de som 42 is?
De som van drie kubussen puzzel, voor het eerst gesteld in 1954 aan de Universiteit van Cambridge en bekend als de Diophantine Vergelijking x3+y3+z3=k, daagde wiskundigen uit om oplossingen te vinden voor getallen 1-100. Bij kleinere getallen is dit type vergelijking gemakkelijker op te lossen: 29 kan bijvoorbeeld worden geschreven als 33 + 13 + 13, terwijl 32 onoplosbaar is. Uiteindelijk zijn ze allemaal opgelost, of onoplosbaar gebleken, met behulp van verschillende technieken en supercomputers, behalve twee getallen: 33 en 42.
Booker bedacht een ingenieus algoritme en bracht weken door op de supercomputer van zijn universiteit toen hij onlangs met een oplossing voor 33 kwam. Maar toen hij zich wendde tot de oplossing voor 42, ontdekte Booker dat de benodigde rekenkracht een orde van grootte hoger was en wellicht de mogelijkheden van zijn supercomputer te boven ging. Booker zegt dat hij veel aanbiedingen van hulp kreeg om het antwoord te vinden, maar in plaats daarvan wendde hij zich tot zijn vriend Andrew “Drew” Sutherland, een hoofdonderzoeker in het Departement van Wiskunde. “Hij is een expert van de wereld in dit soort dingen,” zegt Booker.
Sutherland, wiens specialiteit massaal parallelle berekeningen omvat, brak in 2017 het record voor het grootste Compute Engine-cluster, met 580.000 cores op Preemptible Virtual Machines, het grootste bekende high-performance computing cluster dat in de openbare cloud draait.
Net als andere computationele getaltheoretici die werken in de rekenkundige geometrie, was hij op de hoogte van het “som van drie kubussen” -probleem. En de twee hadden al eerder samengewerkt, bij het helpen opbouwen van de L-functies en Modulaire Vormen Database (LMFDB), een online atlas van wiskundige objecten met betrekking tot wat bekend staat als het Langlands Programma. “Ik was verrukt toen Andy me vroeg om mee te werken aan dit project,” zegt Sutherland.
Booker en Sutherland bespraken de algoritmische strategie die gebruikt zou worden bij het zoeken naar een oplossing voor 42. Zoals Booker had gevonden met zijn oplossing voor 33, wisten ze dat ze niet hun toevlucht hoefden te nemen tot het uitproberen van alle mogelijkheden voor x, y en z.
“Er is een enkele geheel getal parameter, d, die een relatief kleine set mogelijkheden voor x, y en z bepaalt zodanig dat de absolute waarde van z onder een gekozen zoekgrens B ligt,” zegt Sutherland. “In de poging om 33 te kraken was de zoekgrens B 1016, maar deze B bleek te klein om 42 te kraken; in plaats daarvan gebruikten we B = 1017 (1017 is 100 miljoen miljard).
Het belangrijkste verschil tussen de zoektocht naar 33 en de zoektocht naar 42 zou anders de grootte van de zoektocht en het gebruikte computerplatform zijn. Dankzij een genereus aanbod van het Britse Charity Engine konden Booker en Sutherland gebruik maken van de rekenkracht van meer dan 400.000 thuis-pc’s van vrijwilligers over de hele wereld, die elk een reeks waarden voor d kregen toegewezen. De berekeningen op elke PC worden op de achtergrond uitgevoerd, zodat de eigenaar zijn PC nog steeds voor andere taken kan gebruiken.
Sutherland is ook een fan van Douglas Adams, dus het project was onweerstaanbaar.
De methode om Charity Engine te gebruiken lijkt op een deel van het plot rond het getal 42 in de “Hitchhiker”-roman: Nadat Deep Thought’s antwoord van 42 onbevredigend blijkt voor de wetenschappers, die niet weten welke vraag het moet beantwoorden, besluit de supercomputer de Ultieme Vraag te berekenen door een supercomputer te bouwen die wordt aangedreven door de Aarde … met andere woorden, een wereldwijd massaal parallel berekeningsplatform te gebruiken.
“Dit is nog een reden waarom ik het erg leuk vond om deze berekening op Charity Engine uit te voeren – we hebben daadwerkelijk een computer op planetaire schaal gebruikt om een al lang bestaande open vraag op te lossen waarvan het antwoord 42 is.”
Ze voerden een aantal berekeningen uit op een lagere capaciteit om zowel hun code als het Charity Engine-netwerk te testen. Vervolgens gebruikten ze een aantal optimalisaties en aanpassingen om de code beter geschikt te maken voor een massaal gedistribueerde berekening, in vergelijking met een berekening op een enkele supercomputer, zegt Sutherland.
Waarom kon de supercomputer van Bristol dit probleem niet oplossen?
“Nou, elke computer *kan* het probleem oplossen, mits je bereid bent lang genoeg te wachten, maar met ruwweg een half miljoen pc’s die parallel aan het probleem werken (elk met meerdere kernen), waren we in staat om de berekening veel sneller te voltooien dan we hadden kunnen doen met behulp van de Bristol-machine (of een van de machines hier bij MIT),” zegt Sutherland.
Het gebruik van het Charity Engine-netwerk is ook energiezuiniger. “Voor het grootste deel gebruiken we computationele bronnen die anders verloren zouden gaan,” zegt Sutherland. “Wanneer je achter je computer een e-mail leest of aan een spreadsheet werkt, gebruik je slechts een fractie van de beschikbare CPU-bronnen, en de Charity Engine-toepassing, die is gebaseerd op de Berkeley Open Infrastructure for Network Computing (BOINC), maakt hier gebruik van. Als gevolg daarvan is de koolstofvoetafdruk van deze berekening – die verband houdt met de elektriciteit die onze berekeningen de pc’s in het netwerk hebben doen verbruiken boven wat ze hoe dan ook zouden hebben gebruikt – lager dan het geval zou zijn geweest als we een supercomputer hadden gebruikt.”
Sutherland en Booker voerden de berekeningen gedurende verschillende maanden uit, maar de laatste succesvolle run werd in slechts een paar weken voltooid. Toen de e-mail van Charity Engine arriveerde, leverde deze de eerste oplossing voor x3+y3+z3=42:
42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
“Toen ik het nieuws hoorde, was het absoluut een vuistklopmoment,” zegt Sutherland. “Met deze grootschalige berekeningen steek je veel tijd en energie in het optimaliseren van de implementatie, het aanpassen van de parameters, en dan het testen en opnieuw testen van de code gedurende weken en maanden, waarbij je nooit echt weet of al die moeite zich gaat uitbetalen, dus het is uiterst bevredigend wanneer dat wel het geval is.”
Booker en Sutherland zeggen dat er nog 10 getallen, van 101-1000, over zijn om te worden opgelost, met het volgende getal op 114.
Maar beiden zijn meer geïnteresseerd in een eenvoudiger maar rekenkundig uitdagender raadsel: of er meer antwoorden zijn voor de som van drie kubussen voor 3.
“Er zijn vier zeer gemakkelijke oplossingen die bekend waren bij de wiskundige Louis J. Mordell, die in 1953 de volgende beroemde uitspraak deed: “Ik weet niets over de gehele oplossingen van x3 + y3 + z3 = 3 behalve het bestaan van de vier driehoeken (1, 1, 1), (4, 4, -5), (4, -5, 4), (-5, 4, 4); en het moet inderdaad erg moeilijk zijn om iets over andere oplossingen te weten te komen. Dit citaat motiveerde veel van de belangstelling voor het som van drie kubussen probleem, en het geval k=3 in het bijzonder. Hoewel men vermoedt dat er oneindig veel oplossingen moeten zijn, kennen we ondanks meer dan 65 jaar zoeken alleen de gemakkelijke oplossingen die Mordell al kende. Het zou zeer opwindend zijn om nog een oplossing te vinden voor k=3.”