Wiskundigen hebben een nieuwe manier gevonden om grote gehele getallen te vermenigvuldigen. Doordat de methode sneller is dan andere technieken, is dit een baanbrekend resultaat in de computerwetenschap.
De nieuwe techniek is ontwikkeld door David Harvey van de University of New South Wales in Australië en Joris van der Hoeven van de École Polytechnique in Parijs.
Om enigszins te begrijpen hoe de methode werkt, kun je het beste terugdenken aan de handmatige manier van vermenigvuldigen die je op de basisschool hebt geleerd. Je schrijft de twee getallen dan onder elkaar en vermenigvuldigt elk cijfer van het ene getal met elk cijfer van het andere getal. Vervolgens tel je alle nieuwe getallen bij elkaar op.
Als de twee getallen elk n cijfers hebben, vereist deze vermenigvuldigingstechniek grofweg n2 losse berekeningen. ‘De vraag is: kan dat beter?’ zegt wiskundige Joshua Cooper van de University of South Carolina in de VS.
Van maanden naar seconden
In de jaren zestig bewezen wiskundigen dat er inderdaad betere manieren zijn. Eerst ontwikkelde de Rus Anatoly Karatsuba een algoritme dat in hooguit n1,58 stappen een antwoord oplevert. In 1971 vonden de Duitsers Arnold Schönhage en Volker Strassen een manier om het aantal stappen te beperken tot een nog kleiner getal, dat wordt uitgedrukt als n*(log(n))*log(log(n)). Met ‘log’ wordt hier de natuurlijke logaritme aangeduid.
Deze vorderingen hadden veel invloed op computerberekeningen. Een computer die de handmatige vermenigvuldigingsmethode gebruikt, heeft zo’n zes maanden nodig om twee getallen met elk een miljard cijfers te vermenigvuldigen. Met het Schönhage-Strassen-algoritme kan een computer dat in 26 seconden.
Mijlpaal
In hun baanbrekende artikel uit 1971 suggereerden Schönhage en Strassen ook een mogelijke verdere verbetering van hun techniek. Ze deden de prikkelende voorspelling dat vermenigvuldigingen ooit wellicht in hooguit n*log(n) stappen kunnen worden verricht.
Harvey en Van der Hoeven lijken dit nu te hebben bewezen. ‘Eindelijk lijkt het mogelijk’, zegt Cooper. ‘Het heeft de standaardtests doorstaan. Dit is groot nieuws.’
‘Als het resultaat klopt, is dat een grote mijlpaal in de theorie van computationele complexiteit’, zegt Fredrik Johansson van het Franse onderzoeksinstituut INRIA in Bordeaux. ‘De nieuwe ideeën in dit werk zullen waarschijnlijk verder onderzoek inspireren. Ook kunnen ze op termijn tot praktische verbeteringen leiden.’
Belastingteruggaaf
Cooper prijst de originaliteit van het onderzoek. Hij benadrukt bovendien dat de gebruikte wiskunde buitengewoon complex is. ‘Je denkt: jeetje, ik ben alleen maar twee gehele getallen aan het vermenigvuldigen, hoe ingewikkeld kan het worden?’ zegt hij. ‘Maar jongens toch, wat wordt het ingewikkeld.’
Maakt de nieuwe vermenigvuldigingstechniek het makkelijker om je belastingteruggaaf uit te rekenen? ‘Voor mensen die gewoon met pen en papier werken, absoluut niet’, zegt Harvey. Sterker nog, zijn bewijs werkt alleen voor getallen met meer dan 20 triljoen triljoen cijfers. ‘Het woord ‘astronomisch’ schiet hopeloos tekort als je dergelijke getallen probeert te beschrijven’, zegt Harvey.
Snelheidswinst
Toekomstige verbeteringen aan het nieuwe algoritme kunnen het bewijs wellicht doortrekken naar wat behapbaardere getallen met ‘slechts’ een paar biljoen cijfers. ‘We hebben goede hoop dat het nieuwe artikel ons in de praktijk in staat stelt verdere snelheidswinst te boeken’, zegt Van der Hoeven.
Cooper denkt echter dat de werkelijke waarde ervan elders ligt. Volgens hem kunnen programmeurs dankzij dit werk met zekerheid vaststellen hoe lang een algoritme over een bepaalde berekening zal doen.
Harvey denkt dat geen enkel toekomstig algoritme n*log(n) zal kunnen verslaan. ‘Ik zou uitermate verbaasd zijn als dat niet blijkt te kloppen’, zegt hij. ‘Maar goed, er zijn weleens gekkere dingen gebeurd.’
