- Karatsuba samazina lielus reizinājumus no 4 līdz 3, izmantojot dalīšanu un pārvarēšanu, tādējādi pazeminot sarežģītību līdz Θ(n^{1,585}).
- Metode ir balstīta uz x un y sadalīšanu bāzē B, z2, z0 un (x1+x0)(y1+y0) apvienošanu un atkārtotu salikšanu pa B pakāpēm.
- Vēsturiski tas apgāza Kolmogorova hipotēzi un pavēra ceļu Tūma–Kuka un Šēnhāges–Štrāsena hipotēzēm līdz O(n log n) 2019. gadā.
Reizinot mazus skaitļus, mēs to darām tikai galvā, un rezultāts iznāk gandrīz bez domāšanas; ar lieliem skaitļiem lietas mainās, un mēs parasti ķeramies pie papīra, kalkulatora vai programmatūras bibliotēkas. Liels veselu skaitļu reizināšanas skaitlis Tā nav tikai kuriozs: tā ir šifrēšanas, datoralgebras un daudzu datorsistēmu pamatā.
Šajā scenārijā parādās Karatsubas algoritms — izcila ideja, kas samazina nepieciešamo reizināšanu skaitu, dažus aizstājot ar saskaitīšanām un nobīdēm. Knifs ir sadalīt un iekarot. Tam izdodas samazināt klasiskās metodes, kas ir kvadrātiskā metode, sarežģītību līdz zemākai pakāpei, paverot durvis daudz ātrākiem liela mēroga reizinājumiem.
Kāpēc ir svarīgi reizināt ātrāk un klasiskās metodes ierobežojumi
Tradicionālā skolas metode (kolonnu reizināšana) ir viegli saprotama: mēs reizinām katru viena skaitļa ciparu ar katru otra skaitļa ciparu un saskaita dalītās daļas, kas sakārtotas pēc pozīcijas. Ar n-ciparu skaitļiem tas prasa veikt aptuveni n^2 elementāras reizināšanas, kā arī daudzas saskaitīšanas.
Formālāk, standarta procedūra prasa darbību skaitu, kas ir proporcionāls n^2, t.i., Θ(n^2) asimptotiskajā pierakstā. Ja mēs saucam par c1 katras elementārās reizināšanas laiku un c2 par katras saskaitīšanas laiku, vidējo laiku var tuvināti aprēķināt ar c1 n^2 + c2 n^2. Tā kā reizināšana parasti ir sarežģītāka nekā saskaitīšana, lieliem n to var labi tuvināti aprēķināt ar c1 n^2.
Lai to izteiktu skaitļos, iedomāsimies 4572 × 3169, izmantojot tradicionālo metodi. Abiem ir 4 cipari, tāpēc būs 16 elementārreizinājumi un līdzīgs saskaitīšanas skaits, lai uzkrātu daļējos reizinājumus. Šis kvadrātiskais izaugsmes modelis Tas kļūst ļoti apgrūtinoši, mums mērogojot, un tieši šo sašaurinājumu cenšas mazināt ātrie algoritmi.
Vēsturiski tika uzskatīts, ka uzlabojumiem nav daudz iespēju. Intuīcija "ja būtu kaut kas labāks, mēs to jau būtu atraduši" palika savā vietā gadu desmitiem. Tomēr stāsts ieguva dramatisku pavērsienu Maskavas seminārā 1960. gadā.
Vēsture: no Kolmogorova hipotēzes līdz Karatsubas atklāšanai
50. gs. piecdesmitajos gados Andrejs N. Kolmogorovs mēģināja apgalvot, ka klasiskais algoritms ir asimptotiski optimāls; tehniskā ziņā jebkura reizināšanas metode sliktākajā gadījumā prasa Ω(n^2) operācijas. 1960. gada rudenī viņš Maskavas Valsts universitātē organizēja semināru par kibernētiku, kurā dalījās ar šo pieņēmumu un citiem skaitļošanas sarežģītības izaicinājumiem.
Tikai nedēļu vēlāk Anatolijs Karatsuba, toreiz students (saskaņā ar dažādiem avotiem, ar 23 vai 25 gadi), iepazīstināja ar "skaldi un valdi" pieeju, kas veica reizināšanu Θ(n^{log_2 3}) darbības, tas ir, ar eksponentu ≈ 1,585. Tas apgāza Kolmogorova hipotēzi un, kā teikts, viņu ļoti sarūgtināja; viņš pats ziņoja par rezultātu semināra nākamajā un pēdējā sesijā.
Darbs tika publicēts 1962. gadā PSRS Zinātņu akadēmijas rakstos. Raksta, ko, domājams, sarakstījis pats Kolmogorovs (iespējams, kopā ar Juriju Ofmanu), autori ir norādīti kā A. Karatsuba un Yu. OfmensInteresanti, ka Karatsuba par publikāciju uzzināja, kad saņēma žurnāla eksemplāru; viņš nebija iesaistīts redakcijas procesā. Sākot ar 1963. gadu, pēc tulkojuma, tika atbrīvota virkne sasniegumu reizināšanā un ārpus tās.
Kolmogorova sākotnējā aizstāvība, kas bija ļoti ietekmīga viņa prestiža dēļ, bija iekritusi loģiskā slazdā: a arguments ad ignorantiamTas, ka nebija pierādījumu par labāku algoritmu, nenozīmēja, ka tas nevarētu pastāvēt. Karatsuba pierādīja pretējo ar tik vienkāršu, cik spēcīgu ideju.
Karatsubas algoritma skaidrojums
Galvenā ideja ir sadalīt operandus un inteliģenti rekombinēt daļējos produktus. Lai B ir bāze (pozicionālā bāze, kurā mēs rakstām skaitļus) un ņemam divus n-ciparus x un y. Mēs izvēlamies veselu skaitli m ar 0 < m < n un sadalām katru skaitli divās līdzīga lieluma "pusēs":
x = x1·B^m + x0 y y = y1·B^m + y0, ar x0, Un0 < B^m. Ja mēs izstrādājam produktu, mēs iegūstam:
xy = (x1·B^m + x0)(un1·B^m + y0) = z2·B^{2m} + z1·B^m + z0, kur z2 = X.1y1, no1 = X.1y0 + x0y1, no0 = X.0y0Tiešā attīstība izmanto 4 “lielus” reizinājumus.
Karatsuba novēroja, ka z1 var aprēķināt, divreiz nereizinot. Pietiek aprēķināt trīs reizinājumus: z2 = X.1y1, no0 = X.0y0, yt = (x1+x0)(un1+y0)Tad z1 = t − z2 −z0Tādējādi izmaksas palielinās no 4 reizinājumiem līdz tikai 3 reizinājumi (vairāk saskaitīšanas un atņemšanas, kas ir lētākas), un mēs pārveidojam xy kā iepriekš.
Šis pamatsolis darbojas jebkurai B bāzei un jebkurai m, lai gan rekursīvais algoritms vislabāk darbojas, ja m ≈ n/2 (noapaļojot uz augšu). Ja n ir divu pakāpe, un mēs pārtraucam rekursiju, kad n=1, vienciparu reizinājumu skaits ir 3^k, ja n=2^k, tas ir, n^c, kur c = log2(3). Turklāt mēs varam “paplašināt” ar vadošajām nullēm līdz nākamajai divi pakāpei, lai elementāro reizinājumu skaits atbilstu 3^{⌈log2 n⌉} ≤ 3·n^{log2 3}.
Ir nelieli īsceļi: piemēram, ja un1 = 0 (y augšējā puse ir nulle), pietiek ar diviem reizinājumiem, jo z2=0, z0=x0y0, no1=x1y0. Šie deģenerētie gadījumi Tie parādās rekursijas beigās un samazina vēl vairāk darba.
Svarīga praktiska priekšrocība ir tā, ka saskaitīšana, atņemšana un nobīdes par B pakāpēm ir lineāras attiecībā n; to relatīvais svars samazinās, palielinoties n. Recidīva notācijā, ja t(n) ir divu n-ciparu skaitļu reizināšanas kopējās izmaksas, konstantēm c un d varam rakstīt t(n) = 3 t(⌈n/2⌉) + cn + d. Pielietojot galveno teorēmu, iegūstam asimptotisko ierobežojumu t(n) = Θ(n^{log3 / log2}).
Sarežģītība, detalizēts piemērs un praktiska ieviešana
Apskatīsim konkrētu piemēru, izmantojot skaitli ar bāzi 10, lai redzētu mehāniku darbībā. Ņemsim x=1234 un ey=5678, izvēlēsimies B=10 un m=2, tātad 1234 = 12 10^2 + 34 y 5678 = 56 10^2 + 78Mēs aprēķinām trīs Karatsubas “lielos” reizinājumus: z2 = 12 × 56 = 672, z0 = 34 × 78 = 2652, yt = (12 + 34)(56 + 78) = 46 × 134 = 6164. Tad z1 = t − z2 −z0 = 6164 − 672 − 2652 = 2840.
Tagad atliek tikai pārformulēt: xy = z2·B^{2m} + z1·B^m + z0 = 672·10^4 + 2840·10^2 + 2652 = 7.006.652Ar trim galvenajiem reizināšanas darbiem, kā arī saskaitīšanu un decimālskaitļu nobīdēm mēs iegūstam tādu pašu rezultātu kā ar klasisko metodi ar četriem lieliem reizināšanas darbiem.
Algoritms tiek piemērots rekursīvi: katrs no produktiem z2, no0 yt savukārt var aprēķināt, izmantojot Karatsuba, ja operandi joprojām ir lieli. Rekursija apstājas, kad skaitļi ir pietiekami mazi, lai tos varētu reizināt tieši (izmantojot Scholastic metodi vai vietējo CPU reizināšanu).
No arhitektūras viedokļa ir dažas ļoti ērtas bāzes B izvēles. Mašīnā ar pilnu 32x32 bitu ALU reizinātāju, izvēloties B=2^31=2 147 483 648 vai B=10^9=1 000 000 000, katru "ciparu" var saglabāt 32 bitu vārdā. Ar tām bāzēm, x tipa summas1+x0 hei1+y0 Tiem nav nepieciešams papildu pārneses cipars (kā pārneses saglabāšanas summatorā), un mēs varam pielietot rekursiju līdz viena "cipara" bāzes gadījumam.
Ir vērts paturēt prātā, ka maziem n skaitļiem saskaitīšanas un kustību papildu izmaksas var padarīt Karatsuba metodi lēnāku nekā kolonnu metodi. Šķērsošanas vieta Tas ir atkarīgs no platformas un konteksta: kešatmiņas, latentuma, specifiskās ieviešanas… Daži avoti norāda, ka Karatsuba priekšrocība ir milzīga operandu skaita gadījumā (apmēram 2^320 ≈ 2×10^96 vai lielāka), savukārt praksē ar mūsdienu bibliotēkām tā parasti ieslēdzas daudz agrāk ar mēreniem izmēriem; jebkurā gadījumā vienmēr ir slieksnis, virs kura tā kompensējas.
Matemātiski kopējās izmaksas atbilst atkārtošanās principam t(n) = 3·t(⌈n/2⌉) + c·n + d, kura asimptotiskais risinājums ir Θ(n^{log 3 / log 2}) ≈ Θ(n^{1,585}). Uzlabojums salīdzinājumā ar Θ(n^2) nav margināls: dubultojot n, darbs palielinās par koeficientu ≈ 2^{1,585}, nevis 4. Un, ja mums ir jāpiespiež n būt divu pakāpē, pietiek aizpildīt nulles kreisajā pusē; elementāro reizinājumu skaits ir ierobežots ar 3^{⌈log2 n⌉} ≤ 3 n^{logaritms2 3}.
Ārpus Karatsubas, progress turpinājās nemitīgi. Tūms un Kuks (1966) vispārināja ideju un samazināja robežu, un 1971. gadā Šēnhāge un Štrasens ieviesa algoritmu, kura pamatā bija ātrā Furjē transformācija (FFT), lai turpinātu paplašināt robežas. Šie autori arī ierosināja, ka ticamā reizināšanas apakšējā robeža ir n log n kārta.
Pēc vairākām desmitgadēm, 2019. gadā, Deivids Hārvijs un Joriss van der Hēvens iepazīstināja ar metodi, kas sasniedz O(n·log n) laika gaitā, arī paļaujoties uz FFT, bet paplašinot to līdz 1729 dimensijām. Lai gan praktiskais ieguvums, salīdzinot ar citām līdzīgām metodēm, ne vienmēr ir milzīgs un tā sasniegšanai nepieciešami milzīgi izmēri, teorētiskais sasniegums ir milzīgs: pieņemtā robeža ir sasniegta.
Ja jūs interesē, kāpēc Karatsuba netiek mācīta pamatskolā, atbilde ir vienkārša: maziem skaitļiem Klasiskā metode praksē ir optimāla, un Karatsuba papildu slodze nav tā vērta. Tomēr lielas veselu skaitļu bibliotēkas programmēšanas valodās to izmanto; patiesībā tās bieži vien ievieš vairākus algoritmus (klasisko, Karatsuba, Toom-Cook, FFT utt.) un dinamiski izvēlas vispiemērotāko, pamatojoties uz izmēru. Rekursijai virzoties uz mazākiem operandiem, tās pat var "pārslēgt ātrumus" un pabeigt ar standarta reizināšanu.
Lai iedziļinātos, ir ļoti vērtīgi uzziņu avoti: Knuts, Datorprogrammēšanas māksla, 2. sējums, tehniskus rakstus, piemēram, Karatsuba–Ofman, apkopojumus, piemēram, MathWorld un DJ Bernstein piezīmes par daudzciparu reizināšanu, kā arī praktiskus resursus (tiešsaistes kalkulatorus), kas ievieš Karatsuba un tās variantus.
Atsauces un ieteicamā literatūra
- Karakuba AA Berechnungen und die Kompliziertheit von Beziehungen. Elektron. Informationsverarb. Kybernetik 11, 603–606 (1975).
- Knuts DE Datorprogrammēšanas māksla, 2. sējums. Addison-Wesley (1969).
- MathWorld: Karatsubas reizināšana (angļu valodā)
- Bernšteins, dīdžejs Daudzciparu reizināšana matemātiķiem. Karatsubas un citu metožu apskats.
- Karatsubas reizināšana ātrajos algoritmos un FEE; Karatsuba, izmantojot starpības kvadrātus; tiešsaistes kalkulatori, kas to īsteno.
Šī stāsta morāle ir divējāda: no vienas puses, gudra ideja var apgāzt ilgstoši pastāvošus uzskatus; no otras puses, uzlabojums no Θ(n^2) līdz Θ(n^{1,585}) ir pietiekams, lai panāktu taustāmu atšķirību reālās pasaules problēmās, kas saistītas ar gigantiskiem skaitļiem. Tā kā mūsdienu varianti sasniedz O(n log n) un sistēmas izvēlas pareizo algoritmu, pamatojoties uz lielumu, pašreizējā veselu skaitļu reizināšanas ainava ir bagātāka un efektīvāka nekā jebkad agrāk.