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ýš ${\displaystyle n^{\log _{2}3}\approx n^{1,585}}$ jednociferných násobení. Tradiční školský algoritmus násobení přitom vyžaduje ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle x}$ a ${\displaystyle 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 ${\displaystyle x}$ a ${\displaystyle y}$ n-ciferná čísla zapsaná v soustavě o základu z. Pro libovolné přirozené číslo ${\displaystyle m}$ menší než ${\displaystyle n}$ můžeme zadaná čísla zapsat jako

${\displaystyle x=x_{1}z^{m}+x_{0}}$ a

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

kde ${\displaystyle x_{0}}$ a ${\displaystyle y_{0}}$ jsou menší než ${\displaystyle z^{m}}$. Jejich součin je pak

${\displaystyle xy=(x_{1}z^{m}+x_{0})(y_{1}z^{m}+y_{0})}$

${\displaystyle =w_{2}z^{2m}+w_{1}z^{m}+w_{0}}$,

kde

${\displaystyle w_{2}=x_{1}y_{1}}$,

${\displaystyle w_{1}=x_{1}y_{0}+x_{0}y_{1}}$ a

${\displaystyle 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 ${\displaystyle w_{0}}$ a ${\displaystyle w_{2}}$ jako ve vzorcích výše můžeme spočítat

${\displaystyle w_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-w_{2}-w_{0}}$,

čehož pravdivost je zřejmá z:

${\displaystyle w_{1}=x_{1}y_{0}+x_{0}y_{1}}$

${\displaystyle 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 ${\displaystyle z=10}$ a zvolíme ${\displaystyle m=3}$. Činitele rozložíme do podoby:

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

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

${\displaystyle w_{2}=12\cdot 6=72}$

${\displaystyle w_{0}=345\cdot 789=272205}$

${\displaystyle 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í:

${\displaystyle 12345\cdot 6789=w_{2}z^{2m}+w_{1}z^{m}+w_{0}}$, tedy

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

Rekurzivní použití

Mají-li vstupní čísla alespoň ${\displaystyle n\geq 4}$ číslice, pak pomocná násobení podle výše uvedeného postupu pracují s činiteli o méně než ${\displaystyle 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.

Reference

V tomto článku byl použit překlad textu z článku Karatsuba algorithm na anglické Wikipedii.