Algoritmus Karatsuba

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 17. října 2021; kontroly vyžadují 13 úprav .

Násobení Karatsuba je rychlá metoda násobení, která vám umožňuje násobit dvě n -ciferná čísla s bitovou výpočetní složitostí :

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

Vynalezl Anatoly Karatsuba v roce 1960 . Je to historicky první násobící algoritmus, který překonává triviální v asymptotické složitosti [1] [2] [3] [4] .

Historie

V roce 1960 Andrey Kolmogorov uspořádal seminář o matematických problémech kybernetiky. Jedním z úkolů semináře bylo násobení dvoubitových celých čísel. Hlavní známou metodou násobení v té době bylo násobení „ve sloupci“, které při algoritmické implementaci vyžadovalo elementární operace (sčítání nebo násobení jednociferných čísel). Kolmogorov předpokládal, že násobení „ve sloupci“ je optimálním algoritmem pro násobení dvou čísel v tom smyslu, že doba běhu jakékoli metody násobení je přinejmenším řádově velká. Věrohodnost „hypotézy “ naznačoval fakt, že způsob násobení „ve sloupci“ je znám nejméně čtyři tisíciletí, a pokud by existoval rychlejší způsob násobení, pak by se pravděpodobně již našel. O týden později však 23letý Anatolij Karatsuba [5] [6] [7] [8] navrhl novou metodu násobení dvouciferných čísel s odhadem průběžného času a tím vyvrátil „hypotézu “. $n$ $O(n^{2})$ $n^{2}$ $n^{2}$ $n$ $O(n^{\log _{2}3})$ $n^{2}$

Metoda Karatsuba patří k algoritmům „ rozděl a panuj “ spolu s takovými algoritmy jako binární vyhledávání , rychlé řazení atd. Vzorce rekurzivní redukce používané v metodě Karatsuba znal Charles Babbage , který však nevěnoval pozornost možnost použití pouze tří rekurzivních násobení místo čtyř [9] .

Popis metody

Dvoubitová čísla mohou být reprezentována jako , , kde ; . $n$ $a+b$ $cx+d$ ${\displaystyle x=2^{\lceil {n/2}\rceil ))$ ${\displaystyle a,b,c,d<2^{\lceil {n/2}\rceil ))$

Násobení ( bitový posun ) a sčítání se provádějí v konstantním čase . Proto je problém násobení redukován na výpočet koeficientů polynomu . Použití identity ${\displaystyle 2^{\lceil {n/2}\rceil ))$ $O(1)$ $(ax+b)(cx+d)$

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

tento polynom může být reprezentován jako

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

={\color {red}ac}x^{2}+{\color {tmavěoranžová}{\Big (}}{{\color {green}(a+b)(c+d)}-{ \color {červená}ac}-{\barva {modrá}bd}}{\barva {tmavooranžová}{\Velká )))x+{\barva {modrá}bd}\ .

Poslední výraz zahrnuje tři součiny -ciferných čísel. Pokud vypočítáme každý z nich podle stejného schématu, dostaneme algoritmus s rekurzivním odhadem doby běhu $\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})\ .

Pro srovnání, podobný algoritmus, který samostatně provádí všechna čtyři násobení , , , , by vyžadoval obvyklý čas $ac$ $ad$ $před naším letopočtem$ $bd$

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

Příklady

Pro usnadnění prezentace použijeme desítkovou soustavu, tedy argumenty polynomu tvaru místo . Barevné označení čísel nesouvisí s předchozí částí, ale pouze naznačuje, ze kterého čísla je vyčleněna ta či ona část. ${\displaystyle x=10^{k))$ ${\displaystyle x=2^{k))$

Pojďme počítat : ${\color {červená}1213}\cdot {\color {modrá}2311}$

všimněte si a vypočítejte : ${\color {red}12}+{\color {red}13}=25,\ {\color {blue}23}+{\color {blue}11}=34$ ${\displaystyle {\color {tmavěoranžová}25}\cdot {\barva {purpurová}34))$
- všimněte si, že počítáme ${\color {tmavěoranžová}2}+{\barva {tmavěoranžová}5}=7,\ {\barva {purpurová}3}+{\barva {magenta}4}=7$ $7\cdot 7=49$
- vypočítat ${\color {tmavěoranžová}2}\cdot {\color {magenta}3}=6$
- vypočítat ${\color {tmavěoranžová}5}\cdot {\color {purpurová}4}=20$
- když sečteme výsledky, dostaneme to ${\color {tmavěoranžová}25}\cdot {\color {magenta}34}=6\cdot 10^{2}+(49-6-20)\cdot 10+20=850$
vypočítat jako : ${\color {red}12}\cdot {\color {blue}23}$ ${\color {tmavěoranžová}12}\cdot {\barva {purpurová}23}$
- všimněte si, že počítáme ${\color {tmavěoranžová}1}+{\barva {tmavěoranžová}2}=3,\ {\barva {purpurová}2}+{\barva {magenta}3}=5$ $3\cdot 5=15$
- vypočítat ${\color {tmavěoranžová}1}\cdot {\color {magenta}2}=2$
- vypočítat ${\color {tmavěoranžová}2}\cdot {\color {magenta}3}=6$
- když sečteme výsledky, dostaneme to ${\color {tmavěoranžová}12}\cdot {\color {magenta}23}=2\cdot 10^{2}+(15-2-6)\cdot 10+6=276$
vypočítat jako : ${\color {červená}13}\cdot {\color {modrá}11}$ ${\color {tmavěoranžová}13}\cdot {\barva {purpurová}11}$
- všimněte si, že počítáme ${\color {tmavěoranžová}1}+{\barva {tmavěoranžová}3}=4,\ {\barva {purpurová}1}+{\barva {purpurová}1}=2$ $4\cdot 2=8$
- vypočítat ${\color {tmavěoranžová}1}\cdot {\color {purpurová}1}=1$
- vypočítat ${\color {tmavěoranžová}3}\cdot {\color {magenta}1}=3$
- když sečteme výsledky, dostaneme to ${\color {tmavěoranžová}13}\cdot {\color {magenta}11}=1\cdot 10^{2}+(8-1-3)\cdot 10+3=143$
když sečteme výsledky, dostaneme to ${\color {red}1213}\cdot {\color {blue}2311}=276\cdot 10^{4}+(850-276-143)\cdot 10^{2}+143=2803243$

Poznámky

↑ V praxi se algoritmus stává efektivnější než konvenční násobení při násobení čísel o délce řádově stovek binárních (desítek desetinných) číslic, na číslech menší délky algoritmus neposkytuje výraznou výhodu z důvodu větší počet požadovaných sčítání, odečítání a posunu než v naivním algoritmu.
↑ S. A. Gritsenko, E. A. Karatsuba, M. A. Korolev, I. S. Rezvyakova, D. I. Tolev, M. E. Changa. Vědecké úspěchy Anatolije Alekseeviče Karatsuby // Matematika a informatika, 1, K 75. výročí narození Anatolije Alekseeviče Karatsuby, Sovrem. prob. Mat., 16, MIAN, M., 2012, 7–30.
↑ Karatsuba E. A. Fast Algorithms and the BEE Method Archived 4. listopadu 2012 na Wayback Machine , 2008.
↑ Alekseev V. B. Od metody Karatsuba pro rychlé násobení čísel k rychlým algoritmům pro diskrétní funkce // Tr. MIAN. - 1997. - T. 218 . — S. 20–27 .
↑ Karatsuba A., Ofman Yu. Násobení vícehodnotových čísel na automatech // Zprávy Akademie věd SSSR. - 1962. - T. 145 , č. 2 .
↑ Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (německy) // Elektronische Informationsverarbeitung und Kybernetik. - 1975. - Bd. 11 .
↑ Karatsuba A. A. Výpočetní složitost // Tr. MIAN. - 1995. - T. 211 . — S. 186–202 .
↑ Knut D. Umění programování. - 3. vyd. - M .: Williams , 2007. - V. 2. Získané algoritmy. — 832 s. — ISBN 0-201-89684-2 .
↑ A. Shen . Gaussův trik s násobením? // Matematické osvícení . - 2019. - T. 24 . (Ruština)

Odkazy

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin