Karatsuba algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. október 17-én felülvizsgált verziótól ; az ellenőrzések 13 szerkesztést igényelnek .

A Karatsuba szorzás egy gyors szorzási módszer, amely lehetővé teszi két n - jegyű szám szorzását bit számítási bonyolultsággal :

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

Anatolij Karatsuba találta fel 1960- ban . Történelmileg ez az első olyan szorzási algoritmus, amely aszimptotikus összetettségében felülmúlja a triviálist [1] [2] [3] [4] .

Történelem

1960-ban Andrej Kolmogorov szemináriumot tartott a kibernetika matematikai problémáiról. A szemináriumon az egyik feladat a kétbites egész számok szorzása volt . A fő ismert szorzási módszer akkoriban az „oszlopban” szorzás volt, amely algoritmikusan végrehajtva elemi műveleteket (egyjegyű számok összeadását vagy szorzását) igényelte. Kolmogorov feltételezte, hogy az "oszlopban" szorzás az optimális algoritmus két szám szorzására abban az értelemben, hogy bármely szorzási módszer futási ideje legalább egy nagyságrend. A „hipotézis ” valószerűségét jelezte, hogy az „oszlopos” szorzás módszere legalább négy évezrede ismert, és ha lenne gyorsabb szorzási mód, akkor valószínűleg már megtalálták volna. Egy héttel később azonban a 23 éves Anatolij Karatsuba [5] [6] [7] [8] egy új módszert javasolt a kétjegyű számok és a futási idő becsült szorzására, és ezzel megcáfolta a „hipotézist ”. $n$ $O(n^{2})$ $n^{2}$ $n^{2}$ $n$ $O(n^{\log _{2}3})$ $n^{2}$

A Karatsuba módszer az „ oszd meg és uralkodj ” algoritmusokhoz tartozik, olyan algoritmusok mellett, mint a bináris keresés , gyors rendezés stb. A Karatsuba módszerben használt rekurzív redukciós képleteket Charles Babbage ismerte , aki azonban nem figyelt négy helyett csak három rekurzív szorzás használatának lehetősége [9] .

A módszer leírása

A kétbites számok , , ahol ; . $n$ $a+b$ $cx+d$ ${\displaystyle x=2^{\lceil {n/2}\rceil ))$ ${\displaystyle a,b,c,d<2^{\lceil {n/2}\rceil ))$

A szorzás ( biteltolás ) és az összeadás állandó időben történik . Ezért a szorzás problémája a polinom együtthatóinak kiszámítására redukálódik . Az identitás használata ${\displaystyle 2^{\lceil {n/2}\rceil ))$ $O(1)$ ${\megjelenítési stílus (ax+b)(cx+d)}$

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

ezt a polinomot úgy ábrázolhatjuk

(ax+b)(cx+d)={\color {piros}ac}x^{2}+{\color {sötétszín}(ad+bc)}x+{\color {blue}bd}=

={\color {red}ac}x^{2}+{\color {sötét árnyalat}}{\Big (}}{{\color {green}(a+b)(c+d)}-{ \color {red}ac}-{\color {blue}bd}}{\color {sötétszín}{\Big )))x+{\color {blue}bd}\ .

Az utolsó kifejezés a -jegyű számok három szorzatát tartalmazza. Ha mindegyiket ugyanazon séma szerint számítjuk ki, akkor egy algoritmust kapunk a futási idő rekurzív becslésével $\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})\ .

Összehasonlításképpen, egy hasonló algoritmus, amely külön-külön végrehajtja mind a négy szorzást , a , , , a szokásos időt igényelné $ac$ $ad$ $időszámításunk előtt$ $bd$

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

Példák

A bemutatás megkönnyítése érdekében a decimális rendszert, vagyis az alak polinomjának argumentumait használjuk a helyett . A számok színjelölése nem kapcsolódik az előző részhez, csak azt jelzi, hogy melyik számból van kiemelve egy vagy másik rész. ${\displaystyle x=10^{k))$ ${\displaystyle x=2^{k))$

Számoljunk : ${\color {red}1213}\cdot {\color {blue}2311}$

vedd észre és számold ki : ${\color {red}12}+{\color {red}13}=25,\ {\color {blue}23}+{\color {blue}11}=34$ ${\displaystyle {\color {darkorange}25}\cdot {\color {magenta}34))$
- vegye figyelembe, hogy kiszámítjuk ${\color {darkorange}2}+{\color {darkorange}5}=7,\ {\color {magenta}3}+{\color {magenta}4}=7$ $7\cdot 7=49$
- kiszámít ${\color {darkorange}2}\cdot {\color {magenta}3}=6$
- kiszámít ${\color {darkorange}5}\cdot {\color {magenta}4}=20$
- az eredményeket összegezve azt kapjuk ${\color {darkorange}25}\cdot {\color {magenta}34}=6\cdot 10^{2}+(49-6-20)\cdot 10+20=850$
számold ki a következőképpen: ${\color {red}12}\cdot {\color {blue}23}$ ${\color {darkorange}12}\cdot {\color {magenta}23}$
- vegye figyelembe, hogy kiszámítjuk ${\color {darkorange}1}+{\color {darkorange}2}=3,\ {\color {magenta}2}+{\color {magenta}3}=5$ $3\cdot 5=15$
- kiszámít ${\color {darkorange}1}\cdot {\color {magenta}2}=2$
- kiszámít ${\color {darkorange}2}\cdot {\color {magenta}3}=6$
- az eredményeket összegezve azt kapjuk ${\color {darkorange}12}\cdot {\color {magenta}23}=2\cdot 10^{2}+(15-2-6)\cdot 10+6=276$
számold ki a következőképpen: ${\color {red}13}\cdot {\color {blue}11}$ ${\color {darkorange}13}\cdot {\color {magenta}11}$
- vegye figyelembe, hogy kiszámítjuk ${\color {darkorange}1}+{\color {darkorange}3}=4,\ {\color {magenta}1}+{\color {magenta}1}=2$ $4\cdot 2=8$
- kiszámít ${\color {darkorange}1}\cdot {\color {magenta}1}=1$
- kiszámít ${\color {darkorange}3}\cdot {\color {magenta}1}=3$
- az eredményeket összegezve azt kapjuk ${\color {darkorange}13}\cdot {\color {magenta}11}=1\cdot 10^{2}+(8-1-3)\cdot 10+3=143$
az eredményeket összegezve azt kapjuk ${\color {red}1213}\cdot {\color {blue}2311}=276\cdot 10^{4}+(850-276-143)\cdot 10^{2}+143=2803243$

Jegyzetek

↑ A gyakorlatban több száz bináris (tizedesjegyű) nagyságrendű számok szorzásakor az algoritmus hatékonyabb a hagyományos szorzásnál, kisebb hosszúságú számoknál az algoritmus nem nyújt jelentős előnyt, mivel több szükséges összeadás, kivonás és eltolás, mint a naiv algoritmusban.
↑ S. A. Gritsenko, E. A. Karatsuba, M. A. Koroljev, I. S. Rezvyakova, D. I. Tolev, M. E. Changa. Anatolij Alekszejevics Karatsuba tudományos eredményei // Matematika és informatika, 1, Anatolij Alekszejevics Karatsuba születésének 75. évfordulóján, Szovrem. prob. Mat., 16, MIAN, M., 2012, 7–30.
↑ Karatsuba E. A. Fast Algorithms and the BEE Method Archiválva : 2012. november 4., a Wayback Machine , 2008.
↑ Alekseev V. B. A Karatsuba módszertől a számok gyors szorzásához a diszkrét függvények gyors algoritmusaiig // Tr. MIAN. - 1997. - T. 218 . – S. 20–27 .
↑ Karatsuba A., Ofman Yu. Többértékű számok szorzása automatákon // A Szovjetunió Tudományos Akadémiájának jelentései. - 1962. - T. 145 , 2. sz .
↑ Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (német) // Elektronische Informationsverarbeitung und Kybernetik. - 1975. - Bd. 11 .
↑ Karatsuba A. A. Számítási komplexitás // Tr. MIAN. - 1995. - T. 211 . – S. 186–202 .
↑ Knut D. A programozás művészete. - 3. kiadás - M .: Williams , 2007. - V. 2. Megszerzett algoritmusok. — 832 p. — ISBN 0-201-89684-2 .
↑ A. Shen . Gauss szorzási trükk? // Matematikai felvilágosodás . - 2019. - T. 24 . (Orosz)

Linkek

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus