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_23}\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 \Theta\left(n^{\log_23}\right), čímž domněnku vyvrátil. +more 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_1z^m+x_0 a :y=y_1z^m+y_0,

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

:xy=(x_1z^m+x_0)(y_1z^m+y_0) :=w_2z^{2m}+w_1z^m+w_0,

kde

:w_2=x_1y_1, :w_1=x_1y_0+x_0y_1 a :w_0=x_0y_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í. +more 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_1y_0+x_0y_1 :w_1=(x_1+x_0)(y_1+y_0)-x_1y_1-x_0y_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\cdot795-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_2z^{2m} + w_1z^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.

Reference

Kategorie:Počítačová aritmetika