Een getal van 42 cijfers waar wiskundigen al tientallen jaren op jagen omdat het zo moeilijk te berekenen is, is door twee verschillende onderzoeksgroepen tegelijk gevonden. Dit zogeheten dedekind-getal is misschien het laatste van zijn soort die nog berekend kan worden.
Dedekind-getallen beschrijven het aantal manieren waarop verzamelingen van logische bewerkingen kunnen worden gecombineerd. Ze zijn hels moeilijk te berekenen. Sinds 1991 zijn er slechts acht uitgerekend. Nu hebben wiskundigen de negende berekend.
Dubbel exponentieel complex
Eerst wat wiskunde: het dedekind-getal beschrijft het aantal mogelijke ‘monotone booleaanse functies’ met n variabelen. Een booleaanse functie is een functie waarbij de variabelen alleen 0 of 1 (of ‘waar’ of ‘onwaar’) kunnen zijn. ‘Monotoon’ betekent dat als je een een input-variabele van 0 naar 1 verandert, het resultaat niet van 1 naar 0 kan veranderen.
Dit is hoe we wiskundefobie te lijf kunnen gaan
Sarah Hart vertelt hoe we de angst voor getallen en formules weg kunnen nemen.
Voor twee of drie variabelen is het dedekind-getal eenvoudig met de hand te berekenen. Voor grotere n wordt het al snel onmogelijk, omdat het aantal mogelijkheden groeit met een zogenaamde dubbele exponentiële snelheid.
Oud en beroemd probleem
‘2 tot de macht 2 tot de macht n, dat is een zeer ruwe schatting van de complexiteit van dit systeem’, zegt computerwetenschapper Patrick de Causmaecker van de KU Leuven in België. De uitdaging van het berekenen van hogere dedekind-getallen heeft in de loop der jaren onderzoekers uit vele disciplines aangetrokken, van zuivere wiskundigen tot computerwetenschappers. ‘Het is een oud, beroemd probleem. Omdat het moeilijk te kraken is, is het interessant’, zegt wiskundige Christian Jäkel van de Technische Universiteit Dresden in Duitsland.
In 1991 vond wiskundige Doug Wiedemann het achtste dedekind-getal. Daartoe kraakte hij 200 uur lang getallen op een Cray-2-supercomputer, een van de krachtigste machines van dat moment. Niemand kon dit verbeteren, tot nu toe.
‘Ik dacht dat het minstens tien jaar zou duren’
Na zes jaar af en aan aan het probleem te hebben gewerkt, publiceerde Jäkel begin april zijn berekening voor het negende dedekind-getal. Toevallig publiceerden Causmaecker en Lennart van Hirtum, ook aan de KU Leuven, drie dagen later hun werk met hetzelfde resultaat.
Beide groepen kenden elkaar niet. ‘Ik was geschokt, ik wist niet van hun werk. Ik dacht dat het minstens nog tien jaar zou duren om het te berekenen’, zegt Jäkel.
Het resulterende getal is 286.386.577.668.298.411.128.469.151.667.598.498.812.366, een getal van 42 cijfers. Jäkel’s berekening duurde 28 dagen op acht grafische verwerkingseenheden (GPU’s). Om het aantal benodigde berekeningen te verminderen, vermenigvuldigde hij elementen uit de berekening van het veel kleinere vijfde dedekind-getal met elkaar.
Auto-assemblage
Causmaecker en van Hirtum gebruikten een field-programmable gate array (FPGA) voor hun werk, een type processor dat in tegenstelling tot een CPU of een GPU veel verschillende soorten berekeningen tegelijkertijd kan uitvoeren. ‘In een FPGA gebeurt alles altijd tegelijk’, zegt Van Hirtum. ‘Je kunt het vergelijken met een auto-assemblagelijn.’
Net als Jäkel gebruikte het team elementen uit de berekening van kleiner dedekind-getal, in hun geval het zesde. Dit vereiste nog steeds 5,5 biljard bewerkingen, en meer dan vier maanden rekentijd met behulp van de Noctua 2-supercomputer van de Universiteit van Paderborn, zegt van Hirtum.
De meningen zijn verdeeld over de vraag of er ooit nóg een dedekind-getal zal worden gevonden. ‘Het tiende dedekind-getal zal in de orde van 10 tot de macht 82 liggen, waarmee je op het aantal atomen in het zichtbare universum komt. Dus je kunt je voorstellen dat je een enorme technische vooruitgang nodig hebt’, zegt Jäkel.
Energieproductie van de zon
Van Hirtum denkt ook dat de hoeveelheid rekenkracht onpraktisch wordt voor het volgende getal, waarvoor biljoenen extra berekeningen nodig zijn, die samen de volledige energieproductie van de zon zouden opeisen. ‘Deze sprong in complexiteit blijft absoluut astronomisch’, zegt hij.
Maar Causmaecker is positiever. Hij denkt dat nieuwe rekenmethoden de aantallen omlaag kunnen brengen. ‘De combinatie van exponentiële groei van rekenkracht en de kracht van wiskundige algoritmen zal hand in hand gaan. Misschien kunnen we over 20 of 30 jaar dedekind-getal 10 berekenen.’
