- A nagy számok szorzása nehéz. Két német professzor 1971-ben megjósolt egy algoritmust, amely megkönnyíti, de soha senki nem bizonyította be.
- Egészen mostanáig.
- Az ausztrál és francia matematikusok szerint algoritmusukkal sokkal hatékonyabbá tehető a szorzás és másfajta aritmetika.
Az általános iskolától kezdve az összetett szorzás fejfájást okozott. Az ausztráliai New South Wales Sydney-i Egyetem docense azonban egy új módszert dolgozott ki az óriási számok összeszorzására, amely hatékonyabb, mint a “hosszú szorzás”, amit oly sokaknak tanítanak kiskorukban.
“Technikailag bizonyítottuk Schönhage és Strassen 1971-es feltevését az egész számok szorzásának bonyolultságáról” – mondja David Harvey docens az alábbi videóban.
A Schönhage-Strassen algoritmus, amelyet két német matematikus fejlesztett ki, 1971-től 2007-ig valóban a leggyorsabb szorzási módszer volt. Bár 2007-ben kifejlesztettek egy gyorsabb módszert, azt ma már ritkán használják.
Schönhage és Strassen megjósolták, hogy léteznie kell egy n számjegyű számokat n * log(n) alapművelettel szorzó algoritmusnak, mondja Harvey. Az ő dolgozata az első ismert bizonyíték arra, hogy létezik.
Harvey a 314 és 159 szorzatának példáját választja – ez persze nagy egyenlet, de a való életben mindennap használnak ennél sokkal nagyobbakat is. A probléma megoldásához a legtöbb embernek azt tanítják, hogy szorozza össze az egyes számokat, majd adja össze az összegeket:
9-et megszorozzuk 4-gyel, 1-gyel és 3-mal; majd az 5-öt megszorozzuk 4-gyel, 1-gyel és 3-mal, és így tovább. Az eredmény végül 9 számjegyes szorzat lesz.
Ezt a módszert n2-nek vagy n négyzetnek nevezik, mert n-t többször kell n-nel szorozni. Ezzel megkapjuk a helyes választ, de Schönhage és Strassen egy gyorsabb módszert dolgozott ki. Képes volt túllépni az n2-n és valami kisebbre, de még mindig kihívást jelentett az n * log(n).
Néhányaknak elég lehet, ha egy szót látnak egy matematikai feladat közepén, hogy elkerekedjen a szemük, mint az algebraórán. Felfrissítésképpen: a log a logaritmus rövidítése, ami segít az embereknek megfejteni az olyan exponenseket, amelyek számokat négyzetre, kockára vagy még valamivel nagyobbra tesznek. Tehát 2⁵ 32, de logaritmikusan kifejezve úgy nézne ki, hogy log₂(32)=5. Bár szájbarágósnak tűnhet, a logaritmusok döntő fontosságúak, amikor a számok sokkal nagyobbak lesznek.
A Schönhage-Strassen-módszer nagyon gyors, mondja Harvey. Ha egy számítógép az iskolában tanított négyzetes módszert alkalmazná egy olyan problémán, ahol két számnak egyenként egymilliárd számjegye van, az hónapokig tartana. A Schönhage-Strassen-módszert használó számítógép ezt 30 másodperc alatt meg tudná tenni.
De ha a számok folyamatosan a trilliószámokig és még tovább emelkednek, a Harvey és munkatársa, Joris van der Hoeven által a franciaországi École Polytechnique-ben kifejlesztett algoritmus gyorsabban találhat megoldást, mint az 1971-es Schönhage-Strassen algoritmus.
“Ez azt jelenti, hogy mindenféle aritmetikát hatékonyabban lehet elvégezni, például az osztást és a négyzetgyököket” – mondja. “A pi számjegyeit is hatékonyabban ki lehet számolni, mint korábban. Még a hatalmas prímszámokkal kapcsolatos problémákra is van alkalmazása.”
“Az emberek már majdnem 50 éve vadásznak egy ilyen algoritmusra” – folytatja. Nem volt magától értetődő, hogy valaki végül sikerrel jár. Kiderülhetett volna, hogy Schönhage és Strassen tévedett, és hogy ilyen algoritmus nem lehetséges.
“De most már jobban tudjuk” – mondja.