- Het vermenigvuldigen van grote getallen is moeilijk. In 1971 voorspelden twee Duitse professoren een algoritme dat het makkelijker zou maken, maar niemand heeft het ooit bewezen.
- Tot nu.
- Mathematici uit Australië en Frankrijk zeggen dat hun algoritme vermenigvuldigen en andere vormen van rekenen veel efficiënter kan maken.
Vanaf de lagere school is complexe vermenigvuldiging een hoofdpijn geweest. Maar een assistent-professor van de Universiteit van New South Wales Sydney in Australië heeft een nieuwe methode ontwikkeld om reusachtige getallen met elkaar te vermenigvuldigen, die efficiënter is dan het “lange vermenigvuldigen” dat zovelen al op jonge leeftijd wordt geleerd.
“Meer technisch gezien hebben we een vermoeden van Schönhage en Strassen uit 1971 over de complexiteit van het vermenigvuldigen van gehele getallen bewezen,” zegt universitair hoofddocent David Harvey in de video hieronder.
Het Schönhage-Strassen-algoritme, ontwikkeld door twee Duitse wiskundigen, was in feite de snelste methode van vermenigvuldigen van 1971 tot 2007. Hoewel in 2007 een snellere methode werd ontwikkeld, wordt deze tegenwoordig nog maar zelden gebruikt.
Schönhage en Strassen voorspelden dat een algoritme dat n-cijferige getallen vermenigvuldigt met n * log(n) basisbewerkingen zou moeten bestaan, aldus Harvey. Zijn artikel is het eerste bekende bewijs dat het bestaat.
Harvey neemt het voorbeeld van 314 vermenigvuldigd met 159-een grote vergelijking, zeker, maar veel grotere worden elke dag gebruikt in real-life scenario’s. Om het probleem op te lossen, leren de meeste mensen elk getal afzonderlijk met elkaar te vermenigvuldigen, en dan de som op te tellen:
9 wordt vermenigvuldigd met 4, 1, en 3; dan wordt 5 vermenigvuldigd met 4, 1, en 3, enzovoort. Het resultaat eindigt met 9 cijfer-voor-cijfer producten.
Deze methode wordt n2 of n in het kwadraat genoemd, omdat men n een aantal malen met n moet vermenigvuldigen. Het geeft het juiste antwoord, maar Schönhage en Strassen ontwierpen een snellere methode. Zij konden verder gaan dan n2 en naar iets kleiners, maar er diende zich nog steeds een uitdaging aan in de vorm van n * log(n).
Voor sommigen kan het zien van een woord midden in een wiskundeprobleem voldoende zijn om hun ogen te laten verslappen, zoals ze deden in de algebra-les. Om het nog eens op te frissen: log is de afkorting van logaritme, die mensen helpt exponenten te ontcijferen die getallen in het kwadraat, in het kwadraat, in het kwadraat, in het kwadraat of zelfs nog iets hoger maken. Dus 2⁵ is 32, maar logaritmisch uitgedrukt zou het eruit zien als log₂(32)=5. Het lijkt misschien een hele mond vol, maar logaritmen zijn van cruciaal belang als getallen veel groter worden.
De Schönhage-Strassen methode is erg snel, zegt Harvey. Als een computer de kwadraatmethode die hij op school heeft geleerd, zou gebruiken voor een probleem waarbij twee getallen elk een miljard cijfers hebben, zou dat maanden duren. Een computer die de Schönhage-Strassen-methode gebruikt, zou dat in 30 seconden kunnen.
Maar als de getallen blijven oplopen tot in de triljoenen en verder, zou het algoritme dat Harvey en zijn medewerker Joris van der Hoeven aan de École Polytechnique in Frankrijk hebben ontwikkeld, sneller oplossingen kunnen vinden dan het Schönhage-Strassen-algoritme uit 1971.
“Het betekent dat je allerlei rekenkundige bewerkingen efficiënter kunt uitvoeren, bijvoorbeeld delingen en vierkantswortels,” zegt hij. “Je kunt ook de cijfers van pi efficiënter berekenen dan voorheen. Het heeft zelfs toepassingen voor problemen met enorme priemgetallen.
“Mensen zijn al bijna 50 jaar op zoek naar zo’n algoritme”, vervolgt hij. Het was geen uitgemaakte zaak dat iemand uiteindelijk succes zou hebben. Het had kunnen blijken dat Schönhage en Strassen ongelijk hadden, en dat zo’n algoritme niet mogelijk is.
“Maar nu weten we beter,” zegt hij.