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ýš  jednociferných násobení. Tradiční školský algoritmus násobení přitom vyžaduje  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 , čí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  a  pomocí třech násobení menších čísel se zhruba polovinou cifer a několika ciferných posunů a sčítání.

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

 a
,

kde  a  jsou menší než . Jejich součin je pak

,

kde

,
 a

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  a  jako ve vzorcích výše můžeme spočítat

,
čehož pravdivost je zřejmá z:

Příklad 
Při výpočtu součinu 12345 a 6789 máme  a zvolíme . Činitele rozložíme do podoby:
  a
 
K výpočtu součinu nám pak stačí tři násobení na menších číslech:

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

Rekurzivní použití 
Mají-li vstupní čísla alespoň  číslice, pak pomocná násobení podle výše uvedeného postupu pracují s činiteli o méně než  čí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 

Počítačová aritmetika