Karacubovo násobení

Karacubovo násobení je asymptoticky rychlý násobící algoritmus, který v roce 1960 vymyslel sovětský matematik Anatolij Alexejevič Karacuba jako tehdy asymptoticky nejrychlejší algoritmus násobení dlouhých čísel. Jeho složitost je pro dvě n-ciferná čísla nanejvýš $n^{{\log }_{2}3}\approx n^{1,585}$ jednociferných násobení. Tradiční školský algoritmus násobení přitom vyžaduje $n^2$ násobení. Od doby Karacubova objevu byly vymyšleny algoritmy asymptoticky ještě rychlejší, Toomovo-Cookovo násobení a Schönhageovo-Strassenovo násobení. Karacubův algoritmus je přesto stále používán, protože je pro určitou délku vstupních čísel v praxi nejrychlejší.

Dějiny algoritmu

V roce 1952 vyslovil Andrej Nikolajevič Kolmogorov domněnku, že tradiční a tehdy jediný známý školský násobící algoritmus je pro úlohu násobení dlouhých čísel asymptoticky optimální. V roce 1960 pak Kolmogorov organizoval seminář na Lomonosovově univerzitě zaměřený na matematické problémy v kybernetice, kde tehdy třiadvacetiletý student Karacuba vymyslel algoritmus , který násobí dvě n-ciferná čísla v $\mathrm{\Theta }\left(n^{{\log }_{2}3}\right)$, čímž domněnku vyvrátil. Kolmogorova algoritmus zaujal a napsal o něm v roce 1962 do časopisu Doklady Akaděmii Nauk SSSR článek Umnoženije mnogoznačnych čisel na avtomatach, ve kterém zveřejnil také výsledek Jurije Petroviče Ofmana. Jako autoři byli uvedeni „A. Karacuba a Ju. Ofman“, ovšem Karacuba se o článku dozvěděl až s jeho zveřejněním.

Algoritmus

Základní krok

Základním krokem Karacubova algoritmu je vzorec, z kterého vyplývá možnost převést vynásobení dvou čísel $x$ a $y$ pomocí třech násobení menších čísel se zhruba polovinou cifer a několika ciferných posunů a sčítání.

Nechť jsou $x$ a $y$ n-ciferná čísla zapsaná v soustavě o základu z. Pro libovolné přirozené číslo $m$ menší než $n$ můžeme zadaná čísla zapsat jako

$x=x_1{z}^m+x_0$ a

$y=y_1{z}^m+y_0$,

kde $x_0$ a $y_0$ jsou menší než $z^m$. Jejich součin je pak

$xy=(x_1{z}^m+x_0)(y_1{z}^m+y_0)$

$=w_2{z}^{2m}+w_1{z}^m+w_0$,

kde

$w_2=x_1{y}_1$,

$w_1=x_1{y}_0+x_0{y}_1$ a

$w_0=x_0{y}_0$

Tyto vzorce vyžadující čtyři násobení znal už Charles Babbage. Karacuba si povšiml, že za cenu několika sčítání navíc je možné výpočet provést jen pomocí tří násobení. Při $w_0$ a $w_2$ jako ve vzorcích výše můžeme spočítat

$w_1=(x_1+x_0)(y_1+y_0)-w_2-w_0$,

čehož pravdivost je zřejmá z:

$w_1=x_1{y}_0+x_0{y}_1$

$w_1=(x_1+x_0)(y_1+y_0)-x_1{y}_1-x_0{y}_0$

Příklad

Při výpočtu součinu 12345 a 6789 máme $z=10$ a zvolíme $m=3$. Činitele rozložíme do podoby:

• $12345=12\cdot 1000+345$ a
• $6789=6\cdot 1000+789$

K výpočtu součinu nám pak stačí tři násobení na menších číslech:

$w_2=12\cdot 6=72$

$w_0=345\cdot 789=272205$

$w_1=(12+345)(6+789)-w_2-w_0=357\cdot 795-72-272205=11538$

Pomocí těchto součinů už získáme výsledek jen pomocí posunů a sčítání:

$12345\cdot 6789=w_2{z}^{2m}+w_1{z}^m+w_0$, tedy

$72\cdot 1000^2+11538\cdot 1000+272205=83810205$

Rekurzivní použití

Mají-li vstupní čísla alespoň $n\ge 4$ číslice, pak pomocná násobení podle výše uvedeného postupu pracují s činiteli o méně než $n$ číslicích. I na tato pomocná násobení je pak možné využít postup výše a tak rekurzivně dojít až k tak krátkým číslům, pro která komplikovaný postup nenabízí zrychlení a tedy jejich součin spočítáme přímo školským algoritmem.