Algoritmus Karatsuba - Karatsuba algorithm

Karatsuba násobení az + b a cz + d (v rámečku) a 1234 a 567. Purpurové šipky označují násobení, jantarové znamená sčítání, stříbrné označuje odčítání a světle azurové označuje levý posun. (A), (B) a (C) ukazují rekurzi použitou k získání mezilehlých hodnot.

The Algoritmus Karatsuba je rychlý multiplikační algoritmus. Objevil jej Anatoly Karatsuba v roce 1960 a publikován v roce 1962.^[1][2][3] Snižuje násobení dvou n-místná čísla maximálně ${displaystyle n ^ {log _ {2} 3} přibližně n ^ {1,58}}$ jednociferné násobení obecně (a přesně ${displaystyle n ^ {log _ {2} 3}}$ když n je síla 2). Je tedy rychlejší než tradiční algoritmus, který vyžaduje ${displaystyle n ^ {2}}$ jednociferné produkty. Například algoritmus Karatsuba vyžaduje 3¹⁰ = 59 049 jednociferných násobení k vynásobení dvou 1024-místných čísel (n = 1024 = 2¹⁰), zatímco tradiční algoritmus vyžaduje (2¹⁰)² = 1 048 576 (zrychlení 17,75krát).

Algoritmus Karatsuba byl prvním multiplikačním algoritmem asymptoticky rychlejším než kvadratický algoritmus „základní školy“. Algoritmus Toom – Cook (1963) je rychlejší zobecnění Karatsubovy metody a Schönhage – Strassenův algoritmus (1971) je pro rychlejší ještě rychlejší n.

Dějiny

Standardní postup pro násobení dvou n-místná čísla vyžadují několik základních operací úměrných ${displaystyle n ^ {2} ,!}$nebo ${displaystyle O (n ^ {2}) ,!}$ v big-O notace. Andrey Kolmogorov domníval se, že tradiční algoritmus byl asymptoticky optimální, což znamená, že jakýkoli algoritmus pro tento úkol by vyžadoval ${displaystyle Omega (n ^ {2}) ,!}$ základní operace.

V roce 1960 uspořádal Kolmogorov v Matematice seminář o matematických problémech kybernetika na Moskevská státní univerzita, kde uvedl ${displaystyle Omega (n ^ {2}) ,!}$ domněnky a další problémy v EU složitost výpočtu. Během týdne našel Karatsuba, 23letý student, algoritmus (později nazvaný „rozděl a panuj“), který znásobí dva n-místná čísla v ${displaystyle O (n ^ {log _ {2} 3})}$ základní kroky, čímž vyvrací domněnku. Kolmogorov byl z objevu velmi nadšený; sdělil to na příští schůzi semináře, která byla poté ukončena. Kolmogorov přednesl několik přednášek o výsledku Karatsuba na konferencích po celém světě (viz například „Proceedings of the International Congress of Mathematicians 1962“, s. 351–356 a také „6 přednášek přednesených na Mezinárodním kongresu matematiků v Stockholm, 1962 “) a tuto metodu publikoval v roce 1962, v Sborník Akademie věd SSSR. Článek napsal Kolmogorov a obsahoval dva výsledky násobení, Karatsubův algoritmus a samostatný výsledek Jurij Ofman; uvádí jako autory „A. Karatsuba a Yu. Ofman“. Karatsuba se o papíru dozvěděl až poté, co obdržel dotisky od vydavatele.^[2]

Algoritmus

Základní krok

Základním krokem Karatsubova algoritmu je vzorec, který umožňuje vypočítat součin dvou velkých čísel ${displaystyle x}$ a ${displaystyle y}$ pomocí tří násobení menších čísel, každé s přibližně polovinou tolik číslic jako ${displaystyle x}$ nebo ${displaystyle y}$, plus několik dodatků a posunů číslic. Tento základní krok je ve skutečnosti zobecněním podobný komplexní multiplikační algoritmus, Kde imaginární jednotka i je nahrazen výkonem základna.

Nechat ${displaystyle x}$ a ${displaystyle y}$ být reprezentován jako ${displaystyle n}$-místné řetězce v nějaké základně ${displaystyle B}$. Pro jakékoli kladné celé číslo ${displaystyle m}$ méně než ${displaystyle n}$, lze napsat dvě zadaná čísla jako

${displaystyle x = x_ {1} B ^ {m} + x_ {0},}$

${displaystyle y = y_ {1} B ^ {m} + y_ {0},}$

kde ${displaystyle x_ {0}}$ a ${displaystyle y_ {0}}$ jsou menší než ${displaystyle B ^ {m}}$. Produkt je tedy

${displaystyle {egin {aligned} xy & = (x_ {1} B ^ {m} + x_ {0}) (y_ {1} B ^ {m} + y_ {0}) & = z_ {2} B ^ {2m} + z_ {1} B ^ {m} + z_ {0}, end {zarovnáno}}}$

kde

${displaystyle z_ {2} = x_ {1} y_ {1},}$

${displaystyle z_ {1} = x_ {1} y_ {0} + x_ {0} y_ {1},}$

${displaystyle z_ {0} = x_ {0} y_ {0}.}$

Tyto vzorce vyžadují čtyři násobení a byly známy Charles Babbage.^[4] Karatsuba to poznamenal ${displaystyle xy}$ lze vypočítat pouze ve třech násobeních, za cenu několika přídavků navíc. S ${displaystyle z_ {0}}$ a ${displaystyle z_ {2}}$ jako dříve je to možné pozorovat

${displaystyle z_ {1} = (x_ {1} + x_ {0}) (y_ {1} + y_ {0}) - z_ {2} -z_ {0}.}$

Problém, ke kterému však dochází při práci s počítačem ${displaystyle z_ {1}}$ je, že výše uvedený výpočet ${displaystyle (x_ {1} + x_ {0})}$ a ${displaystyle (y_ {1} + y_ {0})}$ může vést k přetečení (způsobí výsledek v rozsahu ${displaystyle B ^ {m} leq {ext {result}} <2B ^ {m}}$), které vyžadují multiplikátor s jedním bitem navíc. Tomu lze zabránit tím, že si to všimneme

${displaystyle z_ {1} = (x_ {0} -x_ {1}) (y_ {1} -y_ {0}) + z_ {2} + z_ {0}.}$

Tento výpočet ${displaystyle (x_ {0} -x_ {1})}$ a ${displaystyle (y_ {1} -y_ {0})}$ vytvoří výsledek v rozsahu ${displaystyle -B ^ {m} <{ext {result}}$. Tato metoda může vytvářet záporná čísla, která vyžadují jeden bit navíc pro zakódování signality, a přesto by pro multiplikátor vyžadovala jeden bit navíc. Jedním ze způsobů, jak tomu zabránit, je zaznamenat znaménko a poté použít absolutní hodnotu ${displaystyle (x_ {0} -x_ {1})}$ a ${displaystyle (y_ {1} -y_ {0})}$ provést nepodepsané násobení, po kterém může být výsledek negován, když se oba znaky původně lišily. Další výhodou je, že i když ${displaystyle (x_ {0} -x_ {1}) (y_ {1} -y_ {0})}$ může být záporný, konečný výpočet ${displaystyle z_ {1}}$ zahrnuje pouze doplňky.

Příklad

Chcete-li vypočítat součin čísel 12345 a 6789, kde B = 10, vyberte m = 3. Používáme m posuny doprava pro rozložení vstupních operandů pomocí výsledné základny (B^m = 1000), tak jako:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

Pouze tři násobení, která fungují na menších celých číslech, se používají k výpočtu tří dílčích výsledků:

z₂ = 12 × 6 = 72

z₀ = 345 × 789 = 272205

z₁ = (12 + 345) × (6 + 789) − z₂ − z₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

Výsledek získáme pouhým přidáním těchto tří dílčích výsledků, odpovídajícím způsobem posunutých (a poté vezmeme v úvahu přenesení těchto tří vstupů v základně 1000 jako pro vstupní operandy):

výsledek = z₂ · (B^m)² + z₁ · (B^m)¹ + z₀ · (B^m)⁰, tj.

výsledek = 72 · 1000² + 11538 · 1000 + 272205 = 83810205.

Všimněte si, že mezilehlé třetí multiplikace pracuje na vstupní doméně, která je méně než dvakrát větší než u dvou prvních multiplikací, její výstupní doména je méně než čtyřikrát větší a base-1000 nese vypočítané z prvních dvou násobení je třeba vzít v úvahu při výpočtu těchto dvou odčítání.

Rekurzivní aplikace

Li n je čtyři nebo více, tři násobení v základním kroku Karatsuby zahrnují operandy s méně než n číslice. Proto lze tyto produkty vypočítat pomocí rekurzivní volání algoritmu Karatsuba. Rekurzi lze použít, dokud nejsou čísla tak malá, že je lze (nebo musí) vypočítat přímo.

V počítači s plným 32bitovým na 32bitovým násobitel dalo by se například vybrat B = 2³¹ = 2147483648a každou číslici uložte jako samostatné 32bitové binární slovo. Pak částky X₁ + X₀ a y₁ + y₀ nebude potřebovat další binární slovo pro uložení číslice přenosu (jako v carry-save zmije ) a lze použít rekurzi Karatsuba, dokud nejsou násobící čísla dlouhá pouze jedna číslice.

Asymetrické vzorce podobné Karatsubě

Karatsubův původní vzorec a další zevšeobecnění jsou samy o sobě symetrické. Například vypočítá následující vzorec

${displaystyle c (x) = c_ {4} x ^ {4} + c_ {3} x ^ {3} + c_ {2} x ^ {2} + c_ {1} x + c_ {0} = a ( x) b (x) = (a_ {2} x ^ {2} + a_ {1} x + a_ {0}) (b_ {2} x ^ {2} + b_ {1} x + b_ {0} )}$

se 6 násobeními v ${displaystyle {ext {GF}} (2) [x]}$, kde ${displaystyle {ext {GF}} (2)}$ je pole Galois se dvěma prvky 0 a 1.

${displaystyle {egin {aligned} left {{egin {array} {l} c_ {0} = p_ {0}, c_ {1} = p_ {012} + p_ {02} + p_ {12} + p_ { 2}, c_ {2} = p_ {012} + p_ {01} + p_ {12}, c_ {3} = p_ {012} + p_ {01} + p_ {02} + p_ {0}, c_ {4} = p_ {2}, konec {pole}} ight.end {zarovnáno}}}$

kde ${displaystyle p_ {i} = a_ {i} b_ {i}, p_ {ij} = (a_ {i} + a_ {j}) (b_ {i} + b_ {j})}$ a ${displaystyle p_ {ijk} = (a_ {i} + a_ {j} + a_ {k}) (b_ {i} + b_ {j} + b_ {k})}$.Upozorňujeme, že sčítání a odčítání je v polích charakteristiky 2 stejné.

Tento vzorec je symetrický, konkrétně se nezmění, pokud vyměníme ${displaystyle a}$ a ${displaystyle b}$ v ${displaystyle p_ {i}, p_ {ij}}$ a ${displaystyle p_ {ijk}}$.

Na základě druhého Zobecněné algoritmy dělení,^[5] Fan et al. našel následující asymetrický vzorec:

${displaystyle {egin {aligned} left {{egin {array} {l} c_ {0} = p_ {0} c_ {1} = p_ {012} + p_ {2} + m_ {4} + m_ {5 } c_ {2} = p_ {012} + m_ {3} + m_ {5} c_ {3} = p_ {012} + p_ {0} + m_ {3} + m_ {4} c_ {4 } = p_ {2}, konec {pole}} ight.end {zarovnáno}}}$

kde ${displaystyle m_ {3} = (a_ {1} + a_ {2}) (b_ {0} + b_ {2}), m_ {4} = (a_ {0} + a_ {1}) (b_ {1 } + b_ {2})}$ a ${displaystyle m_ {5} = (a_ {0} + a_ {2}) (b_ {0} + b_ {1})}$.

Je to asymetrické, protože následující nový vzorec můžeme získat výměnou ${displaystyle a}$ a ${displaystyle b}$ v ${displaystyle m_ {3}, m_ {4}}$ a ${displaystyle m_ {5}}$.

${displaystyle {egin {aligned} left {{egin {array} {l} c_ {0} = p_ {0} c_ {1} = p_ {012} + p_ {2} + m_ {4} + m_ {5 } c_ {2} = p_ {012} + m_ {3} + m_ {5} c_ {3} = p_ {012} + p_ {0} + m_ {3} + m_ {4} c_ {4 } = p_ {2}, konec {pole}} ight.end {zarovnáno}}}$

kde ${displaystyle m_ {3} = (a_ {0} + a_ {2}) (b_ {1} + b_ {2}), m_ {4} = (a_ {1} + a_ {2}) (b_ {0 } + b_ {1})}$ a ${displaystyle m_ {5} = (a_ {0} + a_ {1}) (b_ {0} + b_ {2})}$.

Analýza účinnosti

Základní krok Karatsuby funguje pro jakoukoli základnu B a jakékoli m, ale rekurzivní algoritmus je nejúčinnější, když m je rovný n/ 2, zaokrouhleno nahoru. Zejména pokud n je 2^k, pro celé číslo ka rekurze se zastaví, pouze když n je 1, pak je počet jednociferných násobení 3^k, který je n^C kde C = log₂3.

Jelikož lze rozšířit libovolné vstupy s nulovými číslicemi, dokud jejich délka není síla dvou, vyplývá z toho, že počet elementárních násobení pro libovolné n, je nanejvýš ${displaystyle 3 ^ {lceil log _ {2} nceil} leq 3n ^ {log _ {2} 3} ,!}$.

Od sčítání, odčítání a posunutí číslic (násobení mocninami B) v základním kroku Karatsuby trvá čas úměrný n, jejich náklady se stanou zanedbatelnými, protože n zvyšuje. Přesněji řečeno, pokud t(n) označuje celkový počet základních operací, které algoritmus provádí při vynásobení dvou n- tedy číslice

${displaystyle T (n) = 3T (lceil n / 2ceil) + cn + d}$

pro některé konstanty C a d. Pro tohle relace opakování, hlavní věta o dělení a dobývání opakování dává asymptotické vázaný ${displaystyle T (n) = Theta (n ^ {log _ {2} 3}) ,!}$.

Z toho vyplývá, že pro dostatečně velké n, Karatsubův algoritmus provede méně posunů a jednociferných sčítání než longhandové násobení, i když jeho základní krok používá více sčítání a posunů než přímý vzorec. Pro malé hodnoty n, operace navíc posunu a přidání však mohou způsobit, že běží pomaleji než metoda longhand. Bod pozitivního výnosu závisí na počítačová platforma a kontext. Pravidlem je, že Karatsubova metoda je obvykle rychlejší, když jsou multiplikátory delší než 320–640 bitů.^[6]

Pseudo kód

Zde je pseudokód pro tento algoritmus, který používá čísla představovaná v základní desítce. Pro binární reprezentaci celých čísel stačí nahradit všude 10 čísly 2.^[7]

Druhý argument funkce split_at určuje počet číslic, které se mají extrahovat z že jo: například split_at ("12345", 3) extrahuje 3 poslední číslice, přičemž dává: high = "12", low = "345".

postup karatsuba(num1, num2)    -li (num1 < 10) nebo (num2 < 10)        vrátit se num1 × num2        / * Vypočítá velikost čísel. * /    m = min(size_base10(num1), size_base10(num2))    m2 = podlaha(m / 2)     / * m2 = strop (m / 2) bude také fungovat * /        / * Rozdělte sekvence číslic doprostřed. * /    vysoký1, low1 = split_at(num1, m2)    vysoký2, low2 = split_at(num2, m2)        / * 3 hovory na čísla přibližně poloviční velikosti. * /    z0 = karatsuba(low1, low2)    z1 = karatsuba((low1 + vysoký1), (low2 + vysoký2))    z2 = karatsuba(vysoký1, vysoký2)        vrátit se (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

Reference

externí odkazy

• Karatsubův algoritmus pro polynomiální násobení
• Weisstein, Eric W. "Násobení Karatsuba". MathWorld.
• Bernstein, D. J., "Multiidigitální násobení pro matematiky Pokrývá Karatsuba a mnoho dalších multiplikačních algoritmů.