Karatsuba algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 oktober 2021; kontroller kräver 13 redigeringar .

Karatsuba multiplikation är en snabb multiplikationsmetod som låter dig multiplicera två n -siffriga tal med bitberäkningskomplexitet :

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

Uppfanns av Anatoly Karatsuba 1960 . Det är historiskt sett den första multiplikationsalgoritmen som överträffar den triviala i asymptotisk komplexitet [1] [2] [3] [4] .

Historik

1960 höll Andrey Kolmogorov ett seminarium om kybernetikens matematiska problem. En av uppgifterna som behandlades vid seminariet var multiplikationen av två -bitars heltal. Den främsta kända metoden för multiplikation vid den tiden var multiplikation "i en kolumn", som, när den implementerades algoritmiskt, krävde elementära operationer (additioner eller multiplikationer av ensiffriga tal). Kolmogorov antog att multiplikation "i en kolumn" är den optimala algoritmen för att multiplicera två tal i den meningen att körtiden för en multiplikationsmetod är åtminstone en storleksordning. Sannolikheten för "hypotesen " indikerades av det faktum att multiplikationsmetoden "i en kolumn" har varit känd i minst fyra årtusenden, och om det fanns en snabbare multiplikationsmetod, så skulle den förmodligen redan ha hittats. Men en vecka senare föreslog 23-åriga Anatoly Karatsuba [5] [6] [7] [8] en ny metod för att multiplicera tvåsiffriga tal med en uppskattning av löptiden och motbevisade därmed "hypotesen ". $n$ $O(n^{2})$ $n^{2}$ $n^{2}$ $n$ $O(n^{\log _{2}3})$ $n^{2}$

Karatsuba-metoden tillhör " dela och erövra "-algoritmerna, tillsammans med sådana algoritmer som binär sökning , snabbsortering , etc. De rekursiva reduktionsformler som användes i Karatsuba-metoden var kända för Charles Babbage , som dock inte uppmärksammade möjligheten att använda endast tre rekursiva multiplikationer istället för fyra [9] .

Beskrivning av metoden

Två -bitars nummer kan representeras som , , där ; . $n$ $a+b$ $cx+d$ ${\displaystyle x=2^{\lceil {n/2}\rceil ))$ ${\displaystyle a,b,c,d<2^{\lceil {n/2}\rceil ))$

Multiplikation med ( bitförskjutning ) och addition görs i konstant tid . Därför reduceras problemet med multiplikation till beräkningen av polynomets koefficienter . Använda identiteten ${\displaystyle 2^{\lceil {n/2}\rceil ))$ $O(1)$ $(ax+b)(cx+d)$

{\color {green}(a+b)(c+d)}={\color {red}ac}+{\color {darkrange}(ad+bc)}+{\color {blue}bd }\ ,

detta polynom kan representeras som

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

={\color {red}ac}x^{2}+{\color {darkrange}{\Big (}}{{\color {green}(a+b)(c+d)}-{ \color {red}ac}-{\color {blue}bd}}{\color {darkrange}{\Big )))x+{\color {blue}bd}\ .

Det sista uttrycket involverar tre produkter av -siffriga tal. Om vi beräknar var och en av dem enligt samma schema får vi en algoritm med en rekursiv uppskattning av körtiden $\left({\left\lceil {\frac {n}{2))\right\rceil +1}\right)$

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

Som jämförelse skulle en liknande algoritm som separat utför alla fyra multiplikationerna , , , , kräva den vanliga tiden $ac$ $annons$ $före Kristus$ $bd$

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

Exempel

För att underlätta presentationen kommer vi att använda decimalsystemet, det vill säga argumenten för formens polynom istället för . Siffrornas färgmarkering är inte relaterad till föregående avsnitt, utan anger endast från vilket nummer en eller annan del är utpekad. $x=10^{k}$ ${\displaystyle x=2^{k))$

Låt oss räkna ut : ${\color {red}1213}\cdot {\color {blue}2311}$

notera det och räkna ut : ${\color {red}12}+{\color {red}13}=25,\ {\color {blue}23}+{\color {blue}11}=34$ ${\displaystyle {\color {darkrange}25}\cdot {\color {magenta}34))$
- notera att vi räknar ${\color {darkrange}2}+{\color {darkrange}5}=7,\ {\color {magenta}3}+{\color {magenta}4}=7$ $7\cdot 7=49$
- beräkna ${\color {darkrange}2}\cdot {\color {magenta}3}=6$
- beräkna ${\color {darkrange}5}\cdot {\color {magenta}4}=20$
- summerar vi resultaten så får vi det ${\color {darkrange}25}\cdot {\color {magenta}34}=6\cdot 10^{2}+(49-6-20)\cdot 10+20=850$
beräkna som : ${\color {red}12}\cdot {\color {blue}23}$ ${\color {darkrange}12}\cdot {\color {magenta}23}$
- notera att vi räknar ${\color {darkrange}1}+{\color {darkrange}2}=3,\ {\color {magenta}2}+{\color {magenta}3}=5$ $3\cdot 5=15$
- beräkna ${\color {darkrange}1}\cdot {\color {magenta}2}=2$
- beräkna ${\color {darkrange}2}\cdot {\color {magenta}3}=6$
- summerar vi resultaten så får vi det ${\color {darkrange}12}\cdot {\color {magenta}23}=2\cdot 10^{2}+(15-2-6)\cdot 10+6=276$
beräkna som : ${\color {red}13}\cdot {\color {blue}11}$ ${\color {darkrange}13}\cdot {\color {magenta}11}$
- notera att vi räknar ${\color {darkrange}1}+{\color {darkrange}3}=4,\ {\color {magenta}1}+{\color {magenta}1}=2$ $4\cdot 2=8$
- beräkna ${\color {darkrange}1}\cdot {\color {magenta}1}=1$
- beräkna ${\color {darkrange}3}\cdot {\color {magenta}1}=3$
- summerar vi resultaten så får vi det ${\color {darkrange}13}\cdot {\color {magenta}11}=1\cdot 10^{2}+(8-1-3)\cdot 10+3=143$
summerar vi resultaten så får vi det ${\color {red}1213}\cdot {\color {blue}2311}=276\cdot 10^{4}+(850-276-143)\cdot 10^{2}+143=2803243$

Anteckningar

↑ I praktiken blir algoritmen effektivare än konventionell multiplikation när man multiplicerar tal med en längd av storleksordningen hundratals binära (tiotals decimaler) siffror; på tal med mindre längd ger algoritmen ingen betydande fördel på grund av större antal nödvändiga tillägg, subtraktioner och skiftningar än i den naiva algoritmen.
↑ S. A. Gritsenko, E. A. Karatsuba, M. A. Korolev, I. S. Rezvyakova, D. I. Tolev, M. E. Changa. Vetenskapliga prestationer av Anatoly Alekseevich Karatsuba // Matematik och informatik, 1, På 75-årsdagen av födelsen av Anatoly Alekseevich Karatsuba, Sovrem. prob. Mat., 16, MIAN, M., 2012, 7–30.
↑ Karatsuba E. A. Fast Algorithms and the BEE Method Arkiverad 4 november 2012 på Wayback Machine , 2008.
↑ Alekseev V. B. Från Karatsuba-metoden för snabb multiplikation av tal till snabba algoritmer för diskreta funktioner // Tr. MIAN. - 1997. - T. 218 . — S. 20–27 .
↑ Karatsuba A., Ofman Yu. Multiplikation av siffror med flera värden på automater // Rapporter från USSR:s vetenskapsakademi. - 1962. - T. 145 , nr 2 .
↑ Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (tyska) // Elektronische Informationsverarbeitung und Kybernetik. - 1975. - Bd. 11 .
↑ Karatsuba A. A. Beräkningskomplexitet // Tr. MIAN. - 1995. - T. 211 . — S. 186–202 .
↑ Knut D. Konsten att programmera. - 3:e uppl. - M. : Williams , 2007. - V. 2. Erhållna algoritmer. — 832 sid. — ISBN 0-201-89684-2 .
↑ A. Shen . Gauss multiplikationstrick? // Matematisk upplysning . - 2019. - T. 24 . (ryska)

Länkar

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm