Karatsuba algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 17. oktober 2021; checks kræver 13 redigeringer .

Karatsuba multiplikation er en hurtig multiplikationsmetode, der giver dig mulighed for at multiplicere to n - cifrede tal med bitberegningskompleksitet :

T(n)=O(n^{\log _{2}3}),\quad \log _{2}3=1{,}5849\ldots

Opfundet af Anatoly Karatsuba i 1960 . Det er historisk set den første multiplikationsalgoritme, der overgår den trivielle i asymptotisk kompleksitet [1] [2] [3] [4] .

Historie

I 1960 afholdt Andrey Kolmogorov et seminar om kybernetiks matematiske problemer. En af de opgaver, der blev behandlet på seminaret, var multiplikation af to -bit heltal. Den vigtigste kendte multiplikationsmetode på det tidspunkt var multiplikation "i en kolonne", som, når den blev implementeret algoritmisk, krævede elementære operationer (additioner eller multiplikationer af enkeltcifrede tal). Kolmogorov antog, at multiplikation "i en kolonne" er den optimale algoritme til at multiplicere to tal i den forstand, at køretiden for enhver multiplikationsmetode er mindst en størrelsesorden. Plausibiliteten af "hypotesen " blev indikeret af, at metoden til multiplikation "i en kolonne" har været kendt i mindst fire årtusinder, og hvis der var en hurtigere multiplikationsmetode, så ville den sandsynligvis allerede være fundet. Men en uge senere foreslog 23-årige Anatoly Karatsuba [5] [6] [7] [8] en ny metode til at multiplicere to -cifrede tal med et estimat af køretiden og afviste derved "hypotesen ". $n$ $O(n^{2})$ $n^{2}$ $n^{2}$ $n$ $O(n^{\log _{2}3})$ $n^{2}$

Karatsuba-metoden hører til " del og hersk "-algoritmerne sammen med algoritmer som binær søgning , hurtig sortering osv. De rekursive reduktionsformler, der blev brugt i Karatsuba-metoden, var kendt af Charles Babbage , som dog ikke var opmærksom på muligheden for kun at bruge tre rekursive multiplikationer i stedet for fire [9] .

Beskrivelse af metoden

To -bit tal kan repræsenteres som , , hvor ; . $n$ $a+b$ $cx+d$ ${\displaystyle x=2^{\lceil {n/2}\rceil ))$ $a,b,c,d<2^{\lceil {n/2}\rceil }$

Multiplikation med ( bitforskydning ) og addition sker i konstant tid . Derfor er problemet med multiplikation reduceret til beregningen af polynomiets koefficienter . Brug af identiteten ${\displaystyle 2^{\lceil {n/2}\rceil ))$ $O(1)$ $(ax+b)(cx+d)$

{\color {grøn}(a+b)(c+d)}={\color {rød}ac}+{\color {darkrange}(ad+bc)}+{\color {blå}bd }\ ,

dette polynomium kan repræsenteres som

(ax+b)(cx+d)={\color {red}ac}x^{2}+{\color {darkrange}(ad+bc)}x+{\color {blue}bd}=

={\color {red}ac}x^{2}+{\color {mørkrange}{\Big (}}{{\color {grøn}(a+b)(c+d)}-{ \color {rød}ac}-{\color {blå}bd}}{\color {mørkrange}{\Big )))x+{\color {blå}bd}\ .

Det sidste udtryk involverer tre produkter af -cifrede tal. Hvis vi beregner hver af dem efter samme skema, får vi en algoritme med et rekursivt estimat af køretiden $\left({\left\lceil {\frac {n}{2))\right\rceil +1}\right)$

T(n)=3T\venstre({\frac {n}{2}}\right)+O(n)=O(n^{\log _{2}3})\ .

Til sammenligning ville en lignende algoritme, der hver for sig udfører alle fire multiplikationer , , , , kræve den sædvanlige tid $ac$ $annonce$ $f.Kr$ $bd$

T(n)=4T\venstre({\frac {n}{2}}\right)+O(n)=O(n^{\log _{2}4})=O(n^ {2})\ .

Eksempler

For nemheds skyld vil vi bruge decimalsystemet, det vil sige argumenterne for formens polynomium i stedet for . Numrenes farvemarkering er ikke relateret til det foregående afsnit, men angiver kun fra hvilket nummer den ene eller anden del er udskilt. ${\displaystyle x=10^{k))$ ${\displaystyle x=2^{k))$

Lad os beregne : ${\color {red}1213}\cdot {\color {blue}2311}$

bemærk det og beregn : ${\color {red}12}+{\color {red}13}=25,\ {\color {blue}23}+{\color {blue}11}=34$ ${\displaystyle {\color {darkrange}25}\cdot {\color {magenta}34))$
- bemærk at vi beregner ${\color {darkrange}2}+{\color {darkrange}5}=7,\ {\color {magenta}3}+{\color {magenta}4}=7$ $7\cdot 7=49$
- beregne ${\color {darkrange}2}\cdot {\color {magenta}3}=6$
- beregne ${\color {darkrange}5}\cdot {\color {magenta}4}=20$
- opsummerer resultaterne, får vi det ${\color {darkrange}25}\cdot {\color {magenta}34}=6\cdot 10^{2}+(49-6-20)\cdot 10+20=850$
beregn som : ${\color {red}12}\cdot {\color {blue}23}$ ${\color {darkrange}12}\cdot {\color {magenta}23}$
- bemærk at vi beregner ${\color {darkrange}1}+{\color {darkrange}2}=3,\ {\color {magenta}2}+{\color {magenta}3}=5$ $3\cdot 5=15$
- beregne ${\color {darkrange}1}\cdot {\color {magenta}2}=2$
- beregne ${\color {darkrange}2}\cdot {\color {magenta}3}=6$
- opsummerer resultaterne, får vi det ${\color {darkrange}12}\cdot {\color {magenta}23}=2\cdot 10^{2}+(15-2-6)\cdot 10+6=276$
beregn som : ${\color {red}13}\cdot {\color {blue}11}$ ${\color {darkrange}13}\cdot {\color {magenta}11}$
- bemærk at vi beregner ${\color {darkrange}1}+{\color {darkrange}3}=4,\ {\color {magenta}1}+{\color {magenta}1}=2$ $4\cdot 2=8$
- beregne ${\color {darkrange}1}\cdot {\color {magenta}1}=1$
- beregne ${\color {darkrange}3}\cdot {\color {magenta}1}=3$
- opsummerer resultaterne, får vi det ${\color {darkrange}13}\cdot {\color {magenta}11}=1\cdot 10^{2}+(8-1-3)\cdot 10+3=143$
opsummerer resultaterne, får vi det ${\color {red}1213}\cdot {\color {blue}2311}=276\cdot 10^{4}+(850-276-143)\cdot 10^{2}+143=2803243$

Noter

↑ I praksis bliver algoritmen mere effektiv end konventionel multiplikation, når man multiplicerer tal med en længde af størrelsesordenen hundredvis af binære (tiere decimaler) cifre; på tal med en mindre længde giver algoritmen ikke en væsentlig fordel pga. større antal nødvendige additioner, subtraktioner og forskydninger end i den naive algoritme.
↑ S. A. Gritsenko, E. A. Karatsuba, M. A. Korolev, I. S. Rezvyakova, D. I. Tolev, M. E. Changa. Anatoly Alekseevich Karatsubas videnskabelige resultater // Matematik og informatik, 1, På 75-årsdagen for Anatoly Alekseevich Karatsubas fødsel, Sovrem. sandsynlighed Mat., 16, MIAN, M., 2012, 7-30.
↑ Karatsuba E. A. Fast Algorithms and the BEE Method Arkiveret 4. november 2012 på Wayback Machine , 2008.
↑ Alekseev V. B. Fra Karatsuba-metoden til hurtig multiplikation af tal til hurtige algoritmer for diskrete funktioner // Tr. MIAN. - 1997. - T. 218 . — S. 20–27 .
↑ Karatsuba A., Ofman Yu. Multiplikation af tal med flere værdier på automater // Rapporter fra USSRs Videnskabsakademi. - 1962. - T. 145 , nr. 2 .
↑ Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (tysk) // Elektronische Informationsverarbeitung und Kybernetik. - 1975. - Bd. 11 .
↑ Karatsuba A. A. Beregningsmæssig kompleksitet // Tr. MIAN. - 1995. - T. 211 . — S. 186–202 .
↑ Knut D. Kunsten at programmere. - 3. udg. - M. : Williams , 2007. - V. 2. Opnåede algoritmer. — 832 s. — ISBN 0-201-89684-2 .
↑ A. Shen . Gauss multiplikationstrick? // Matematisk oplysning . - 2019. - T. 24 . (Russisk)

Links

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme