- Karatsuba az osztás és meghódítás módszerével 4-ről 3-ra csökkenti a nagy szorzásokat, így a bonyolultságot Θ(n^{1,585})-re csökkenti.
- A módszer az x és y B alapú felbontásán, z2, z0 és (x1+x0)(y1+y0) kombinálásán, majd a B hatványaival történő újrabontásán alapul.
- Történelmileg megdöntötte a Kolmogorov-sejtést, és utat nyitott a Toom–Cook és a Schönhage–Strassen sejtéseknek egészen az O(n log n)-ig 2019-ben.
Amikor kis számokat szorzunk, azt csak fejben megtehetjük, és szinte gondolkodás nélkül kijön; nagy számoknál a dolgok megváltoznak, és általában papírhoz, számológéphez vagy szoftverkönyvtárhoz folyamodunk. A nagy egész számokkal való szorzás nem csupán kuriózum: a titkosítás, a számítógépes algebra és számos számítási rendszer középpontjában áll.
Ebben a forgatókönyvben születik meg Karatsuba algoritmusa, egy zseniális ötlet, amely csökkenti a szükséges szorzások számát azáltal, hogy néhányat összeadással és eltolással helyettesít. Az oszd meg és uralkodj trükk a klasszikus, kvadratikus módszer bonyolultságát alacsonyabb hatványra csökkenti, megnyitva az utat a sokkal gyorsabb, nagy léptékű szorzások előtt.
Miért fontos a gyorsabb szorzás, és a klasszikus módszer korlátai
A hagyományos iskolai módszer (oszlopszorzás) könnyen érthető: az egyik szám minden számjegyét megszorozzuk a másik minden számjegyével, és az egymáshoz igazított törteket összegezzük. N számjegyű tag esetén ez arra kényszerít minket, hogy körülbelül an^2 elemi szorzásokat végezzünk, számos összeadás mellett.
Formálisabban, a standard eljárás az an^2-vel arányos számú műveletet igényel, azaz aszimptotikus jelöléssel Θ(n^2) . Ha c1-nek nevezzük az egyes elemi szorzások idejét, c2-nek pedig az egyes összeadások idejét, akkor az átlagos idő közelíthető c1·n^2 + c2·n^2-vel. Mivel a szorzás általában időigényesebb, mint az összeadás, nagy n esetén jól közelíthető c1·n^2 -vel.
Számokban kifejezve, vegyük a 4572 × 3169-et a hagyományos módszerrel. Mindkettő négyjegyű, tehát 16 elemi szorzatra és hasonló számú összegre lesz szükség a parciálisok összegyűjtéséhez. Ez a kvadratikus növekedési minta hihetetlenül nehézkessé válik a skálázás során, és pontosan ezt a szűk keresztmetszetet próbálják a gyors algoritmusok enyhíteni.
Történelmileg úgy gondolták, hogy nincs sok lehetőség a fejlődésre. Az a megérzés, hogy „ha lenne valami jobb, már megtaláltuk volna”, évtizedekig megmaradt. A történelem azonban drámai fordulatot vett egy 1960-as moszkvai szemináriumon.
Történelem: Kolmogorov sejtésétől Karatsuba felfedezéséig
Az 50-es években Andrej N. Kolmogorov megpróbálta azt állítani, hogy a klasszikus szorzóalgoritmus aszimptotikusan optimális; technikai értelemben véve, hogy bármely szorzási módszer a legrosszabb esetben is Ω(n^2) műveletet igényel. 1960 őszén kibernetikai szemináriumot szervezett a Moszkvai Állami Egyetemen, ahol megosztotta ezt a feltételezést és a számítási komplexitás egyéb kihívásait.
Mindössze egy héttel később Anatolij Karatsuba, aki akkor diák volt (különböző források szerint 23 vagy 25 éves ), bemutatott egy osztás-és-meghatározás módszert, amely Θ(n^{log_2 3}) műveletekkel, azaz ≈ 1,585 kitevővel végezte a szorzást. Ez megdöntötte Kolmogorov sejtését, és a történet szerint nagyon csalódott volt; ő maga ismertette az eredményt a szeminárium következő és egyben utolsó ülésén.
A mű 1962-ben jelent meg a Szovjetunió Tudományos Akadémia folyóiratában. A feltehetően maga Kolmogorov által írt (valószínűleg Jurij Ofmannal közösen) cikk A. Karatsubát és Yu. Ofmant tüntette fel szerzőként . Érdekes módon Karatsuba csak akkor értesült a kiadványról, amikor megkapta a folyóirat egy példányát; akkor még nem vett részt a szerkesztési folyamatban. 1963-tól kezdődően, miután lefordították, a mű a szorzástudomány és azon túli területek fejlődésének özönét indította el.
Kolmogorov eredeti védekezése, amely presztízse miatt nagy befolyással bírt, logikai csapdába esett: egy tudatlanságból fakadó érvelésbe . A jobb algoritmusra vonatkozó bizonyítékok hiánya nem jelentette azt, hogy nem létezhet. Karatsuba egy egyszerű, de hatásos ötlettel bebizonyította az ellenkezőjét.
A Karatsuba algoritmus magyarázata
A központi gondolat az operandusok szétválasztása és a parciális szorzatok intelligens újrakombinálása. Legyen B egy bázis (a pozicionális bázis, amelyben a számokat írjuk), és vegyük két n jegyű számot, x-et és y-t. Válasszunk egy m egész számot, ahol 0 < m < y, és mindkét számot két hasonló méretű "fele" részre osztjuk:
x = x 1 ·B^m + x 0 és y = y 1 ·B^m + y 0 , ahol x 0 , y 0 < B^m. Ha a szorzatot kifejtjük, a következőt kapjuk:
xy = (x 1 ·B^m + x 0 )(y 1 ·B^m + y 0 ) = z 2 ·B^{2m} + z 1 ·B^m + z 0 , ahol z 2 = x 1 y 1 , z 1 = x 1 y 0 + x 0 y 1 , z 0 = x 0 y 0 . A direkt kiterjesztés 4 „nagy” szorzást használ.
Karatsuba megfigyelte, hogy z1 keresztszorzás nélkül is kiszámítható. Elegendő három szorzatot kiszámítani: z2 = x1y1 , z0 = x0y0 , yt = ( x1 + x0 ) ( y1 + y0 ) . Ekkor z1 = t − z2 − z0 . Ezzel a költség 4 szorzásról mindössze 3 szorzásra csökken ( plusz az összeadások és kivonások, amelyek olcsóbbak), és az xy-t a korábbiakhoz hasonlóan újraírjuk.
Ez az alaplépés tetszőleges B alapú számrendszerre és tetszőleges m számrendszerre működik, bár a rekurzív algoritmus jobban teljesít, ha m ≈ n/2 (felfelé kerekítés). Ha n kettő hatványa , és a rekurziót n=1-nél állítjuk le, akkor az egyjegyű szorzatok száma 3^k, ha n=2^k, azaz n^c, ahol c = log₂ ( 3). Továbbá a kezdő nullákkal "kiterjeszthetjük" a következő kettő hatványáig, így az elemi szorzások száma kielégíti a 3^{log₂ ( n)} ≤ 3^{log₂ ( 3)} feltételt.
Vannak apró rövidítések: ha például y 1 = 0 (az y felső fele nulla), akkor két szorzat elegendő, mivel z 2 = 0, z 0 = x 0 y 0 , z 1 = x 1 y 0. Ezek a degenerált esetek a rekurzió végén jelennek meg, és még több munkát igényelnek.
Egy fontos gyakorlati előny, hogy B összegei, differenciái és hatványeltolódásai lineárisak n-ben; relatív súlyuk csökken n növekedésével. Rekurziós jelöléssel , ha t(n) két n-jegyű szám szorzásának teljes költsége, akkor a c és d konstansok esetén t(n) = 3·t(⌈n/2⌉) + c·n + d alakot írhatjuk. A főtétel alkalmazásával a t(n) = Θ(n^{log 3 / log 2}) aszimptotikus korlátot kapjuk.
Komplexitás, részletes példa és gyakorlati megvalósítás
Nézzünk egy konkrét, 10-es alapú példát, hogy lássuk a mechanikát működés közben. Vegyük x=1234 és ey=5678. A B=10-et és az ym=2-t választjuk, tehát 1234 = 12·10^2 + 34 és 5678 = 56·10^2 + 78. Kiszámítjuk a három "nagy" Karatsuba-szorzatot: z2 = 12×56 = 672, z0 = 34×78 = 2652, és yt = (12+34)(56+78) = 46×134 = 6164. Ekkor z1 = t − z2 − z0 = 6164 − 672 − 2652 = 2840.
Most már csak át kell rendeznünk: xy = z 2 ·B^{2m} + z 1 ·B^m + z 0 = 672·10^4 + 2840·10^2 + 2652 = 7 006 652. Három fő szorzással, plusz összeadással és tizedes eltolással ugyanarra az eredményre jutunk, mint a klasszikus módszerrel négy nagy szorzással.
Az algoritmust rekurzívan alkalmazzák: a z2 , z0 és t szorzatok mindegyike kiszámítható a Karatsuba segítségével, amikor az operandusok még mindig nagyok. A rekurzió leáll, amikor a számok elég kicsik ahhoz, hogy közvetlenül szorozhatók legyenek (iskolai módszer vagy natív CPU-szorzás).
Architekturális szempontból a B bázisnak van néhány nagyon kényelmes választási lehetősége. Egy teljes 32×32 bites ALU szorzóval rendelkező gépben a B=2^31=2 147 483 648 vagy a B=10^9=1 000 000 000 kiválasztása lehetővé teszi, hogy minden "számjegyet" egy 32 bites szóban tároljunk. Ezekkel az alapokkal az x1 + x0 vagy y1 + y0 alakú összegek nem igényelnek extra átviteli számjegyet (mint egy átvitel-mentő összeadóban), és rekurziót alkalmazhatunk egyetlen "számjegy" alapesetéig.
Érdemes szem előtt tartani, hogy kis n értékek esetén az összeadások és áthelyezések többletterhelése a Karatsubát lassabbá teheti, mint az oszlopmetódus. Az átmenet pontja a platformtól és a kontextustól függ: gyorsítótárak, késleltetések, adott implementáció stb. Egyes források a Karatsuba előnyét nagyon nagy operandusok esetén tartják fontosnak (nagyságrendileg 2^320 ≈ 2×10^96 vagy nagyobb), míg a gyakorlatban a modern könyvtárak általában sokkal korábban aktiválódnak mérsékelt méretekkel; mindenesetre mindig van egy küszöbérték, amelyen túl érdemes használni.
Matematikailag a teljes költség kielégíti a t(n) = 3·t(⌈n/2⌉) + c·n + d rekurziós relációt , melynek aszimptotikus megoldása Θ(n^{log3 / log2}) ≈ Θ(n^{1,585}). A Θ(n^2)-hez képesti javulás nem marginális: n megduplázásával a munka ≈ 2^{1,585} faktorral nő a 4 helyett. És ha arra kell kényszerítenünk, hogy n a kettő hatványa legyen, akkor egyszerűen ki kell egészítenünk nullákkal a bal oldalon; az elemi szorzások számát a 3^{⌈log2n⌉ } ≤ 3·n^{log23 } korlátja.
Karatsubán túl a fejlődés nem állt meg. Toom és Cook (1966) általánosították az ötletet és leszűkítették a korlátot, majd 1971-ben Schönhage és Strassen bevezettek egy gyors Fourier-transzformáción (FFT) alapuló algoritmust a határok további feszegetésére. Ezek a szerzők azt is felvetették, hogy a szorzásra a valószínűsíthető alsó korlát n log n nagyságrendű.
Évtizedekkel később, 2019-ben David Harvey és Joris van der Hoeven bemutattak egy módszert, amely időben O(n log n) értéket ér el , szintén az FFT-re támaszkodva, de 1729 dimenzióra kiterjesztve azt. Bár a gyakorlati előny más hasonló módszerekhez képest nem mindig óriási, és kolosszális méretekre van szükség az igazi érvényesüléshez, az elméleti eredmény lenyűgöző: a sejtett határt elérték.
Ha azon tűnődsz, hogy miért nem tanítják a Karatsubát az általános iskolában, a válasz egyszerű: kis számok esetén a klasszikus módszer a gyakorlatban optimális, és a Karatsuba többletterhelése ezt nem kompenzálja. A programozási nyelvekben található nagy egészértékű könyvtárak azonban használják; sőt, gyakran több algoritmust is megvalósítanak (klasszikus, Karatsuba, Toom-Cook, FFT stb.), és dinamikusan választják ki a méret alapján a legmegfelelőbbet. Ahogy a rekurzió a kisebb operandusok felé halad, akár „sebességet is válthatnak”, és a standard szorzással fejezhetik be.
További tanulmányozáshoz értékes referenciaforrások állnak rendelkezésre: Knuth, The Art of Computer Programming, 2. kötet , szakmai cikkek, mint például Karatsuba–Ofmané, összefoglalók, mint például a MathWorld és DJ Bernstein jegyzetei a többjegyű szorzásról, valamint gyakorlati források (online számológépek), amelyek megvalósítják a Karatsubát és variánsait.
Hivatkozások és ajánlott olvasmányok
- Karakuba AA Berechnungen und die Kompliziertheit von Beziehungen. Elektron. Informationsverarb. Kybernetik 11, 603–606 (1975).
- Knuth DE A számítógépes programozás művészete, 2. kötet. Addison–Wesley (1969).
- MathWorld: Karatsuba szorzás (angolul)
- Bernstein, DJ Többjegyű szorzás matematikusoknak. A Karatsuba és más módszerek áttekintése.
- Karatsuba szorzás gyors algoritmusokban és a FEE-ben; Karatsuba különbségnégyzet használatával; online számológépek, amelyek megvalósítják.
A történet tanulsága kettős: egyrészt egy ötletes megoldás mélyen gyökerező hiedelmeket dönthet meg; másrészt a Θ(n^2)-ről Θ(n^{1,585})-re való javulás elegendő ahhoz, hogy kézzelfogható különbséget jelentsen a hatalmas számokkal kapcsolatos valós problémákban. A modern, O(n log n)-t elérő változatokkal és a méret alapján legmegfelelőbb algoritmust választó rendszerekkel az egész számok szorzásának jelenlegi tájképe gazdagabb és hatékonyabb, mint valaha.