- Karatsuba vähendab suuri korrutustehinguid jagamise ja valitsemise abil 4-lt 3-le, langetades keerukuse Θ(n^{1,585}-ni).
- Meetod põhineb x ja y lahutamisel baasis B, z2, z0 ja (x1+x0)(y1+y0) kombineerimisel ning uuesti komponeerimisel B astmete abil.
- Ajalooliselt lükkas see ümber Kolmogorovi hüpoteesi ja sillutas teed Toom-Cooki ja Schönhage-Strassenile kuni O(n log n)-ni 2019. aastal.
Väikeste arvude korrutamisel saame seda teha lihtsalt peas ja tulemus tuleb välja peaaegu mõtlemata; suurte arvude puhul asjad muutuvad ja me tavaliselt pöördume paberi, kalkulaatori või tarkvarateegi poole. Suurte täisarvudega korrutamine pole lihtsalt kurioosum: see on krüpteerimise, arvutialgebra ja paljude arvutussüsteemide keskmes.
Selles stsenaariumis ilmneb Karatsuba algoritm – geniaalne idee, mis vähendab vajalike korrutuste arvu, asendades mõned neist liitmiste ja nihutamistega. Jaga-ja-valitse nipp alandab klassikalise ruutmeetodi keerukust madalamale astmele, avades ukse palju kiirematele korrutustehingutele laiaulatuslikult.
Miks on kiirem korrutamine oluline ja klassikalise meetodi piirid
Traditsiooniline koolimeetod (veergude järgi korrutamine) on lihtne mõista: me korrutame ühe arvu iga numbri teise arvu iga numbriga ja summeerime positsiooni järgi joondatud osaarvud. n numbrit kuus sunnib see meid lisaks paljudele liitmistele tegema umbes an^2 elementaarseid korrutustehte.
Formaalsemalt öeldes nõuab standardprotseduur arvu tehteid, mis on proportsionaalsed an^2-ga, st asümptootilises tähistuses Θ(n^2) . Kui nimetame c1 iga elementaarse korrutamise ajaks ja c2 iga liitmise ajaks, saab keskmise aja lähendada valemiga c1·n^2 + c2·n^2. Kuna korrutamine on tavaliselt aeganõudvam kui liitmine, on see suure n korral hästi lähendatud valemiga c1·n^2.
Numbritesse pannes vaatleme traditsioonilise meetodi abil suurust 4572 × 3169. Mõlemal on neli numbrit, seega on osasummade kogumiseks 16 elementaarkorrutist ja sarnane arv summasid. See ruutkasvumuster muutub skaleerimisel uskumatult kohmakaks ja just seda kitsaskohta püüavad kiired algoritmid leevendada.
Ajalooliselt arvati, et arenguruumi pole palju. Intuitsioon, et "kui oleks midagi paremat, oleksime selle juba leidnud", püsis aastakümneid. Ajalugu võttis aga dramaatilise pöörde 1960. aastal Moskvas toimunud seminaril.
Ajalugu: Kolmogorovi hüpoteesist Karatsuba avastamiseni
50. aastatel püüdis Andrei N. Kolmogorov väita, et klassikaline korrutamisalgoritm on asümptootiliselt optimaalne; tehnilises mõttes, et iga korrutamismeetod nõuab halvimal juhul Ω(n^2) tehteid. 1960. aasta sügisel korraldas ta Moskva Riiklikus Ülikoolis küberneetika seminari, kus ta jagas seda eeldust ja teisi arvutusliku keerukusega seotud väljakutseid.
Vaid nädal hiljem esitles tollal tudeng Anatoli Karatsuba (erinevate allikate kohaselt 23- või 25-aastane ) jaga-ja-valitse meetodit, mis sooritas korrutamist Θ(n^{log_2 3}) tehtes, st astendajaga ≈ 1,585. See lükkas Kolmogorovi hüpoteesi ümber ja, nagu jutt käib, valmistas talle suure pettumuse; ta ise edastas tulemuse seminari järgmises ja viimases sessioonis.
Teos avaldati 1962. aastal ajakirjas Toimetised NSVL Teaduste Akadeemias. Artiklis, mille arvatavasti kirjutas Kolmogorov ise (võimalik, et koos Juri Ofmaniga), olid autoritena märgitud A. Karatsuba ja Yu. Ofman . Huvitaval kombel sai Karatsuba avaldamisest teada alles siis, kui ta sai ajakirja eksemplari; ta polnud toimetamisprotsessis osalenud. Alates 1963. aastast, pärast tõlkimist, pani teos aluse edusammudele korrutamises ja kaugemalgi.
Kolmogorovi algne kaitseargument, mis oli tema prestiiži tõttu väga mõjukas, oli langenud loogilisse lõksu: teadmatusest tulenev argument . Parema algoritmi tõendite puudumine ei tähendanud, et seda ei saaks eksisteerida. Karatsuba tõestas vastupidist ideega, mis oli sama lihtne kui võimas.
Karatsuba algoritmi selgitus
Keskne idee on operandide dekompositsioon ja osakorrutiste intelligentne rekombineerimine. Olgu B baas (positsioonibaas, kuhu me numbreid kirjutame) ja võtame kaks n-kohalist arvu x ja y. Valime täisarvu m, kus 0 < m < y, ja jagame iga arvu kaheks sarnase suurusega "pooleks":
x = x 1 ·B^m + x 0 ja y = y 1 ·B^m + y 0 , kus x 0 , y 0 < B^m. Kui me korrutist laiendame, saame:
xy = (x 1 ·B^m + x 0 )(y 1 ·B^m + y 0 ) = z 2 ·B^{2m} + z 1 ·B^m + z 0 , kus z 2 = x 1 y 1 , z 1 = x 1 y 0 + x 0 y 1 , z 0 = x 0 y 0 . Otsearendus kasutab nelja "suurt" korrutust.
Karatsuba täheldas, et z1 saab arvutada ilma ristkorrutusteta. Piisab kolme korrutise arvutamisest: z2 = x1y1 , z0 = x0y0 , yt = ( x1 + x0 ) ( y1 + y0 ) . Siis z1 = t − z2 − z0 . Sellega langeb maksumus 4 korrutamiselt ainult 3 korrutamisele ( lisaks liitmised ja lahutamised, mis on odavamad) ning me komponeerime xy uuesti nagu varem.
See põhisamm töötab mis tahes baasarvu B ja mis tahes m korral, kuigi rekursiivne algoritm toimib paremini, kui m ≈ n/2 (ümardamine ülespoole). Kui n on kahe aste ja me peatame rekursiooni, kui n=1, siis ühekohaliste korrutiste arv on 3^k, kui n=2^k, st n^c, kus c = log₂ ( 3). Lisaks saame "laiendada" algsete nullidega kuni järgmise kahe astmeni, nii et elementaarkorrutuste arv rahuldab tingimust 3^{log₂ ( n)} ≤ 3^{log₂ ( 3)}.
On väikeseid otseteid: kui näiteks y 1 = 0 (y ülemine pool on null), siis piisab kahest korrutisest, kuna z 2 = 0, z 0 = x 0 y 0 , z 1 = x 1 y 0. Need degenereerunud juhtumid ilmnevad rekursiooni lõpus ja vähendavad veelgi tööd.
Oluline praktiline eelis on see, et B summad, diferentsid ja astmenihked on n suhtes lineaarsed; nende suhteline kaal väheneb n suurenedes. Rekurrentses tähistuses , kui t(n) on kahe n-kohalise arvu korrutamise kogumaksumus, saame konstantide c ja d korral kirjutada t(n) = 3·t(⌈n/2⌉) + c·n + d. Põhiteoreemi rakendades saame asümptootilise seose t(n) = Θ(n^{log 3 / log 2}).
Keerukus, detailne näide ja praktiline rakendamine
Vaatame konkreetset näidet, mis põhineb kümnendsüsteemil, et näha mehaanikat tegevuses. Võtame x=1234 ja ey=5678. Valime B=10 ja ym=2, seega 1234 = 12·10^2 + 34 ja 5678 = 56·10^2 + 78. Arvutame kolm "suurt" Karatsuba korrutist: z2 = 12×56 = 672, z0 = 34×78 = 2652 ja yt = (12+34)(56+78) = 46×134 = 6164. Siis z1 = t − z2 − z0 = 6164 − 672 − 2652 = 2840.
Nüüd peame lihtsalt ümber korraldama: xy = z 2 ·B^{2m} + z 1 ·B^m + z 0 = 672·10^4 + 2840·10^2 + 2652 = 7 006 652. Kolme peamise korrutustehte, liitmiste ja kümnendmurdude nihutamisega jõuame sama tulemuseni kui klassikalise meetodi puhul, mis kasutab nelja suurt korrutustehte.
Algoritmi rakendatakse rekursiivselt: kõiki korrutisi z2 , z0 ja t saab omakorda arvutada Karatsuba abil, kui operandid on endiselt suured. Rekursioon peatub, kui arvud on piisavalt väikesed, et neid otse korrutada (koolimeetod või protsessori natiivne korrutamine).
Arhitektuurilisest seisukohast on baasi B jaoks mõned väga mugavad valikud. Masinas, millel on täielik 32×32-bitine ALU kordistaja, võimaldab B=2^31=2 147 483 648 või B=10^9=1 000 000 000 valimine iga "numbri" salvestada 32-bitisesse sõnasse. Nende baaside korral ei vaja x1 + x0 või y1 + y0 kujulised summad täiendavat kandenumbrit (nagu kandevõimega liitjas) ja me saame rakendada rekursiooni kuni ühe "numbri" baasjuhtumini.
Tasub meeles pidada, et väikeste n väärtuste korral võib liitmiste ja liigutamiste lisakoormus muuta Karatsuba aeglasemaks kui veerumeetod. Üleminekupunkt sõltub platvormist ja kontekstist: vahemälud, latentsused, konkreetne implementatsioon jne. Mõned allikad peavad Karatsuba eeliseks väga suurte operandide puhul (suurusjärgus 2^320 ≈ 2×10^96 või suuremad), samas kui praktikas aktiveeritakse tänapäevased teegid tavaliselt palju varem ja mõõduka suurusega; igal juhul on alati olemas lävi, millest alates see otstarbekaks muutub.
Matemaatiliselt rahuldab kogumaksumus rekurrentseerust t(n) = 3·t(⌈n/2⌉) + c·n + d , mille asümptootiline lahend on Θ(n^{log 3 / log 2}) ≈ Θ(n^{1,585}). Paremus võrreldes Θ(n^2)-ga ei ole marginaalne: n kahekordistamisel suureneb töö ≈ 2^{1,585} korda, mitte 4. Ja kui peame sundima n olema kahe astmes, peame selle lihtsalt vasakule nullidega täitma; elementaarsete korrutuste arv on piiratud 3^{⌈log 2 n⌉} ≤ 3·n^{log 2 3}.
Pärast Karatsubat progress ei peatunud. Toom ja Cook (1966) üldistasid ideed ja alandasid piiri ning 1971. aastal tutvustasid Schönhage ja Strassen kiirel Fourier' teisendusel (FFT) põhinevat algoritmi, et piire veelgi nihutada. Need autorid pakkusid ka välja, et korrutamise usutav alumine piir on järku n log n.
Aastakümneid hiljem, 2019. aastal, esitlesid David Harvey ja Joris van der Hoeven meetodit, mis saavutab ajas O(n log n) , tuginedes samuti FFT-le, kuid laiendades seda 1729 dimensioonini. Kuigi praktiline kasu võrreldes teiste sarnaste meetoditega pole alati tohutu ja tõeliseks säramiseks on vaja kolossaalseid suurusi, on teoreetiline saavutus märkimisväärne: oletatav piir on saavutatud.
Kui teid huvitab, miks Karatsubat algkoolis ei õpetata, on vastus lihtne: väikeste arvude puhul on klassikaline meetod praktikas optimaalne ja Karatsuba lisakulud seda ei kompenseeri. Programmeerimiskeelte suured täisarvuteegid seda aga kasutavad; tegelikult rakendavad nad sageli mitut algoritmi (klassikaline, Karatsuba, Toom-Cook, FFT jne) ja valivad dünaamiliselt suuruse põhjal kõige sobivama. Rekursiooni edenedes väiksemate operandide poole, saavad nad isegi "käiku vahetada" ja lõpetada standardse korrutamisega.
Edasiseks uurimiseks on väärtuslikke teabeallikaid: Knuth, The Art of Computer Programming, 2. köide , tehnilised artiklid nagu Karatsuba-Ofmani oma, kogumikud nagu MathWorld ja DJ Bernsteini märkmed mitmekohalise korrutamise kohta, samuti praktilised ressursid (veebikalkulaatorid), mis rakendavad Karatsubat ja selle variante.
Viited ja soovitatav kirjandus
- Karakuba AA Berechnungen und die Kompliziertheit von Beziehungen. Elektron. Informationsverarb. Kybernetik 11, 603–606 (1975).
- Knuth DE Arvutiprogrammeerimise kunst, 2. kd. Addison-Wesley (1969).
- MathWorld: Karatsuba korrutamine (inglise keeles)
- Bernstein, DJ Mitmekohaline korrutamine matemaatikutele. Karatsuba ja teiste meetodite ülevaade.
- Karatsuba korrutamine kiiretes algoritmides ja FEE-s; Karatsuba ruutude vahe abil; veebikalkulaatorid, mis seda rakendavad.
Selle loo moraal on kahetine: ühelt poolt võib leidlik idee kummutada sügavalt juurdunud uskumusi; teiselt poolt on paranemine Θ(n^2)-lt Θ(n^{1,585})-ni piisav, et tuua reaalsetes probleemides tohutute arvudega käegakatsutavaid tulemusi. Kuna tänapäevased variandid ulatuvad O(n log n)-ni ja süsteemid valivad suuruse põhjal kõige sobivama algoritmi, on täisarvude korrutamise praegune maastik rikkalikum ja tõhusam kui kunagi varem.