- Det er svært at multiplicere store tal. I 1971 forudsagde to tyske professorer en algoritme, der ville gøre det lettere, men ingen har nogensinde bevist det.
- Indtil nu.
- Matematikere fra Australien og Frankrig siger, at deres algoritme kan gøre multiplikation og andre former for aritmetik meget mere effektiv.
Fra grundskolen og fremefter har kompleks multiplikation været en hovedpine. Men en assisterende professor fra University of New South Wales Sydney i Australien har udviklet en ny metode til at gange gigantiske tal sammen, som er mere effektiv end den “lange multiplikation”, som så mange får lært i en tidlig alder.
“Mere teknisk set har vi bevist en formodning fra Schönhage og Strassen fra 1971 om kompleksiteten af heltalsmultiplikation,” siger lektor David Harvey i videoen nedenfor.
Sønhage-Strassen-algoritmen, der er udviklet af to tyske matematikere, var faktisk den hurtigste metode til multiplikation fra 1971 til 2007. Selv om der blev udviklet en hurtigere metode i 2007, bruges den sjældent i dag.
Schönhage og Strassen forudsagde, at en algoritme, der multiplicerer n-cifrede tal ved hjælp af n * log(n) grundoperationer, skulle eksistere, siger Harvey. Hans artikel er det første kendte bevis for, at det gør den.
Harvey vælger eksemplet 314 ganget med 159 – en stor ligning, ganske vist, men langt større ligninger anvendes hver dag i virkelige situationer. For at løse problemet lærer de fleste mennesker at gange hvert enkelt tal sammen og derefter lægge summen sammen:
9 ganges med 4, 1 og 3; derefter ganges 5 med 4, 1 og 3 og så videre. Resultatet ender med at give 9 cifrede produkter.
Denne metode kaldes n2 eller n kvadreret, fordi man skal gange n med n et antal gange. Den vil give det korrekte svar, men Schönhage og Strassen har designet en hurtigere metode. Den var i stand til at bevæge sig ud over n2 og ind i noget mindre, men der var stadig en udfordring i form af n * log(n).
For nogle kan det at se et ord midt i et matematisk problem være nok til at få øjnene til at blive glaserede, som de gjorde i algebraundervisningen. Som en genopfriskning: log er en forkortelse for logaritme, som hjælper folk med at tyde eksponenter, der gør tal til kvadrater eller terninger eller endda noget højere. Så 2⁵ er 32, men udtrykt logaritmisk ville det se ud som log₂(32)=5. Selv om det kan virke som en mundfuld, er logaritmer afgørende, når tal bliver meget større.
Den Schönhage-Strassen-metode er meget hurtig, siger Harvey. Hvis en computer skulle bruge den kvadrerede metode, som man lærer i skolen, på et problem, hvor to tal havde en milliard cifre hver, ville det tage måneder. En computer, der anvender Schönhage-Strassen-metoden, kunne gøre det på 30 sekunder.
Men hvis tallene bliver ved med at stige til trillioner og derover, vil algoritmen, som Harvey og samarbejdspartner Joris van der Hoeven har udviklet på École Polytechnique i Frankrig, kunne finde løsninger hurtigere end Schönhage-Strassen-algoritmen fra 1971.
“Det betyder, at man kan udføre alle former for aritmetik mere effektivt, f.eks. division og kvadratrødder”, siger han. “Man kan også beregne cifre af pi mere effektivt end tidligere. Det har endda anvendelsesmuligheder for problemer med store primtal.”
“Folk har været på jagt efter en sådan algoritme i næsten 50 år,” fortsætter han. Det var ikke en selvfølge, at det i sidste ende ville lykkes for nogen. Det kunne have vist sig, at Schönhage og Strassen tog fejl, og at en sådan algoritme ikke er mulig.
“Men nu ved vi bedre,” siger han.