- Det är svårt att multiplicera stora tal. År 1971 förutspådde två tyska professorer en algoritm som skulle göra det lättare, men ingen har någonsin bevisat det.
- Tills nu.
- Matematiker från Australien och Frankrike säger att deras algoritm kan göra multiplikation och andra typer av aritmetik mycket effektivare.
Från grundskolan och framåt har komplex multiplikation varit en huvudvärk. Men en biträdande professor vid University of New South Wales Sydney i Australien har utvecklat en ny metod för att multiplicera jättestora tal tillsammans som är effektivare än den ”långa multiplikation” som så många får lära sig i tidig ålder.
”Mer tekniskt sett har vi bevisat en gissning från 1971 av Schönhage och Strassen om komplexiteten hos multiplikation av heltal”, säger biträdande professor David Harvey i videon nedan.
Sönhage-Strassen-algoritmen, som utvecklades av två tyska matematiker, var faktiskt den snabbaste multiplikationsmetoden från 1971 till 2007. Även om en snabbare metod utvecklades 2007 används den sällan idag.
Schönhage och Strassen förutspådde att en algoritm som multiplicerar n-siffriga tal med hjälp av n * log(n) grundläggande operationer skulle finnas, säger Harvey. Hans artikel är det första kända beviset för att den gör det.
Harvey väljer exemplet 314 multiplicerat med 159 – en stor ekvation, men mycket större ekvationer används varje dag i verkliga scenarier. För att lösa problemet får de flesta människor lära sig att multiplicera varje enskilt tal tillsammans och sedan addera summorna:
9 multipliceras med 4, 1 och 3; sedan multipliceras 5 med 4, 1 och 3, och så vidare. Resultatet slutar med 9 siffermässiga produkter.
Denna metod kallas n2 eller n i kvadrat, eftersom man måste multiplicera n med n ett antal gånger. Den ger rätt svar, men Schönhage och Strassen utformade en snabbare metod. Den kunde gå bortom n2 och till något mindre, men en utmaning presenterade sig fortfarande i form av n * log(n).
För vissa kan det räcka med att se ett ord mitt i ett matematiskt problem för att få ögonen att rinna över som de gjorde på algebraundervisningen. Som en uppfriskning: log är en förkortning för logaritm, vilket hjälper människor att tyda exponenter som gör tal till kvadrater eller kuber eller till och med något högre. Så 2⁵ är 32, men uttryckt logaritmiskt skulle det se ut som log₂(32)=5. Även om det kan verka som en munsbit är logaritmer avgörande när talen blir mycket större.
Skönhage-Strassen-metoden är mycket snabb, säger Harvey. Om en dator skulle använda kvadreringsmetoden som lärs ut i skolan på ett problem där två tal har en miljard siffror vardera skulle det ta månader. En dator som använder Schönhage-Strassen-metoden skulle kunna göra det på 30 sekunder.
Men om siffrorna fortsätter att stiga till triljoner och längre kan den algoritm som Harvey och samarbetspartnern Joris van der Hoeven vid École Polytechnique i Frankrike utvecklat hitta lösningar snabbare än Schönhage-Strassen-algoritmen från 1971.
”Det innebär att man kan göra alla typer av aritmetik effektivare, till exempel division och kvadratrötter”, säger han. ”Man kan också beräkna siffrorna för pi effektivare än tidigare. Den har till och med tillämpningar på problem med enorma primtal.
”Folk har varit på jakt efter en sådan algoritm i nästan 50 år”, fortsätter han. Det var inte självklart att någon så småningom skulle lyckas. Det kunde ha visat sig att Schönhage och Strassen hade fel och att ingen sådan algoritm är möjlig.
”Men nu vet vi bättre”, säger han.