- Suurten lukujen kertominen on vaikeaa. Vuonna 1971 kaksi saksalaista professoria ennusti algoritmin, joka helpottaisi sitä, mutta kukaan ei koskaan todistanut sitä.
- Kunnes nyt.
- Australialaiset ja ranskalaiset matemaatikot sanovat, että heidän algoritminsa voi tehdä kertolaskusta ja muista aritmeettisista laskutoimituksista paljon tehokkaampia.
Kompleksinen kertolasku on aiheuttanut päänvaivaa peruskoulusta lähtien. Mutta apulaisprofessori Uuden Etelä-Walesin Sydneyn yliopistosta Australiassa on kehittänyt uuden menetelmän jättimäisten lukujen yhteenlaskemiseen, joka on tehokkaampi kuin ”pitkä kertolasku”, jota niin monille opetetaan jo varhain.
”Teknisesti ottaen olemme todistaneet Schönhagen ja Strassenin vuonna 1971 esittämän arvelun kokonaislukujen kertolaskun monimutkaisuudesta”, apulaisprofessori David Harvey sanoo alla olevalla videolla.
Kahden saksalaisen matemaatikon kehittämä Schönhage-Strassen-algoritmi oli itse asiassa nopein kertolaskumenetelmä vuodesta 1971 vuoteen 2007. Vaikka vuonna 2007 kehitettiin nopeampi menetelmä, sitä käytetään nykyään harvoin.
Schönhage ja Strassen ennustivat, että n-numeroisia lukuja kertova algoritmi, joka käyttää n * log(n) perusoperaatiota, pitäisi olla olemassa, Harvey sanoo. Hänen artikkelinsa on ensimmäinen tunnettu todiste siitä, että se on olemassa.
Harvey valitsee esimerkin 314 kerrottuna 159:llä – tämä on toki suuri yhtälö, mutta paljon suurempia yhtälöitä käytetään joka päivä tosielämän tilanteissa. Ongelman ratkaisemiseksi useimmat ihmiset opetetaan kertomaan jokainen yksittäinen luku yhteen ja laskemaan sitten summat yhteen:
9 kerrotaan luvuilla 4, 1 ja 3; sitten 5 kerrotaan luvuilla 4, 1 ja 3 ja niin edelleen. Lopputuloksena on 9 numeroitua tuotetta.
Tätä menetelmää kutsutaan n2:ksi tai n:n neliöksi, koska on kerrottava n moninkertaisesti n:llä. Sillä saadaan oikea vastaus, mutta Schönhage ja Strassen suunnittelivat nopeamman menetelmän. Sillä pystyttiin siirtymään n2:sta johonkin pienempään, mutta haasteena oli edelleen n * log(n).
Joidenkin kohdalla sanan näkeminen keskellä matemaattista tehtävää saattaa riittää siihen, että heidän silmänsä lasittuvat kuten algebran tunnilla. Virkistykseksi: log on lyhenne sanoista logaritmi, joka auttaa ihmisiä tulkitsemaan eksponentteja, jotka tekevät luvuista neliöitä tai kuutioita tai jopa jotain suurempia. 2⁵ on siis 32, mutta logaritmisesti ilmaistuna se näyttäisi log₂(32)=5. Vaikka se saattaa tuntua suupaltilta, logaritmit ovat ratkaisevan tärkeitä, kun luvut kasvavat paljon suuremmiksi.
Schönhage-Strassen-menetelmä on erittäin nopea, Harvey sanoo. Jos tietokone käyttäisi koulussa opetettua neliömenetelmää ongelmaan, jossa kahdessa luvussa on miljardi numeroa kummassakin, se veisi kuukausia. Schönhage-Strassenin menetelmää käyttävä tietokone voisi tehdä sen 30 sekunnissa.
Mutta jos luvut jatkavat nousuaan triljooniin ja pidemmälle, Harveyn ja yhteistyökumppaninsa Joris van der Hoevenin École Polytechniquessa Ranskassa kehittämä algoritmi voisi löytää ratkaisut nopeammin kuin vuoden 1971 Schönhage-Strassen-algoritmi.
”Se tarkoittaa, että kaikenlaista aritmeettista laskentaa voidaan tehdä tehokkaammin, esimerkiksi jakamista ja neliöjuuria”, hän sanoo. ”Voit myös laskea piin luvut aiempaa tehokkaammin. Sillä on jopa sovelluksia ongelmiin, joihin liittyy valtavia alkulukuja.”
”Tällaista algoritmia on metsästetty lähes 50 vuotta”, hän jatkaa. Ei ollut itsestäänselvyys, että joku lopulta onnistuisi. Olisi saattanut käydä ilmi, että Schönhage ja Strassen olivat väärässä, eikä sellaista algoritmia olekaan.
”Mutta nyt tiedämme paremmin”, hän sanoo.