Алгоритм Карацубы

Умножение Карацубы — метод быстрого умножения, позволяющий перемножать два ${\displaystyle n}$-значных числа с битовой вычислительной сложностью ${\displaystyle T(n)=O(n^{\log _{2}3})}$.

Изобретён Анатолием Карацубой в 1960 году. Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности^[1][2][3][4].

В 1960 году Колмогоров проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало умножение двух ${\displaystyle n}$-разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало ${\displaystyle O(n^{2})}$ элементарных операций (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что время работы любого метода умножения не меньше ${\displaystyle n^{2}}$ по порядку величины. На правдоподобность «гипотезы ${\displaystyle n^{2}}$» указывало то, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, через неделю 23-летний Карацуба^[5][6][7][8] предложил новый метод умножения двух ${\displaystyle n}$-значных чисел с оценкой времени работы ${\displaystyle O(n^{\log _{2}3})}$ и тем самым опроверг «гипотезу ${\displaystyle n^{2}}$».

Метод Карацубы относится к алгоритмам вида «разделяй и властвуй», наравне с такими алгоритмами как двоичный поиск, быстрая сортировка и др. Формулы рекурсивного сведения, используемые в методе Карацубы, были известны ещё Чарльзу Бэббиджу, который, однако, не обратил внимания на возможность использования лишь трёх рекурсивных умножений вместо четырёх^[9].

Два ${\displaystyle n}$-битовых числа можно представить в виде ${\displaystyle ax+b}$, ${\displaystyle cx+d}$, где ${\displaystyle x=2^{\lceil {n/2}\rceil }}$ и ${\displaystyle a,b,c,d<2^{\lceil {n/2}\rceil }}$.

Умножение на ${\displaystyle 2^{\lceil {n/2}\rceil }}$ (битовый сдвиг) и сложение делаются за постоянное время ${\displaystyle O(1)}$. Поэтому задача умножения сводится к вычислению коэффициентов многочлена ${\displaystyle (ax+b)(cx+d)}$. Используя тождество:

${\displaystyle {\color {green}(a+b)(c+d)}={\color {red}ac}+{\color {darkorange}(ad+bc)}+{\color {blue}bd}\ }$,

этот многочлен можно представить в виде:

${\displaystyle (ax+b)(cx+d)={\color {red}ac}x^{2}+{\color {darkorange}(ad+bc)}x+{\color {blue}bd}=}$

${\displaystyle ={\color {red}ac}x^{2}+{\color {darkorange}{\Big (}}{{\color {green}(a+b)(c+d)}-{\color {red}ac}-{\color {blue}bd}}{\color {darkorange}{\Big )}}x+{\color {blue}bd}}$.

В последнем выражении участвуют три произведения ${\displaystyle \left({\left\lceil {\frac {n}{2}}\right\rceil +1}\right)}$-значных чисел. Если вычислять каждое из них по той же схеме, получится алгоритм с рекуррентной оценкой времени работы:

${\displaystyle T(n)=3T\left({\frac {n}{2}}\right)+O(n)=O\left(n^{\log _{2}3}\right)}$.

Для сравнения, аналогичный алгоритм, производящий отдельно все четыре умножения ${\displaystyle ac}$, ${\displaystyle ad}$, ${\displaystyle bc}$, ${\displaystyle bd}$, требовал бы обычного времени:

${\displaystyle T(n)=4T\left({\frac {n}{2}}\right)+O(n)=O\left(n^{\log _{2}4}\right)=O\left(n^{2}\right)}$.

Для умножения двух восьмизначных (в десятичной записи) чисел ${\displaystyle N=11113333}$ и ${\displaystyle M=55557777}$ каждое из них представляется в виде суммы двух чисел вдвое меньшей разрядности, одно из которых взято со сдвигом^[10]:

${\displaystyle {\begin{cases}N=1111\cdot 10000+3333\\M=5555\cdot 10000+7777\end{cases}}}$

Раскрывая скобки, произведение ${\displaystyle N}$ и ${\displaystyle M}$ можно переписать как:

${\displaystyle (1111\cdot 10000+3333)(5555\cdot 10000+7777)=1111\cdot 5555\cdot 10000^{2}+10000(1111\cdot 7777+5555\cdot 3333)+3333\cdot 7777}$

Карацуба нашёл, что вместо четырёх умножений вдвое более коротких чисел, можно делать лишь три: ${\displaystyle 1111\cdot 5555}$, ${\displaystyle (1111+3333)\cdot (5555+7777)}$ и ${\displaystyle 3333\cdot 7777}$, в результате чего выражение преобразуется к виду:

${\displaystyle 1111\cdot 5555\cdot 10000^{2}+10000((1111+3333)\cdot (5555+7777)-1111\cdot 5555-3333\cdot 7777)+3333\cdot 7777}$.

Для умножения укороченных вдвое чисел применяется тот же алгоритм: ${\displaystyle 1111\cdot 5555}$ представляется как ${\displaystyle (11\cdot 100+11)(55\cdot 100+55)}$ и так далее. На практике для достаточно коротких чисел применяется уже обычное умножение как более эффективное.

Подход работает в любой системе счисления, в том числе и в двоичной, используемой вычислительной техникой. Например, вычисление произведения двух 4096-битных двоичных чисел методом Карацубы требует ${\displaystyle 3^{12}\approx 5,3\cdot 10^{5}}$ элементарных однобитовых умножений вместо ${\displaystyle (2^{12})^{2}\approx 1,68\cdot 10^{7}}$ при умножении наивным методом.

• http://212.cmc-msu.ru/files/kniga.html
• https://web.archive.org/web/20071031012910/http://gersoo.free.fr/docs/karat/kar.html
• http://numbers.computation.free.fr/Constants/Algorithms/representation.html
• https://web.archive.org/web/20160417193210/http://www-math.uni-paderborn.de/mca/mult.html
• http://www-2.cs.cmu.edu/~cburch/251/karat/
• http://www.cs.pitt.edu/~kirk/cs1501/animations/
• https://web.archive.org/web/20070125091442/http://www.cs.princeton.edu/introcs/79crypto/Karatsuba.java.html
• http://www.ccas.ru/personal/karatsuba/divcru.htm
• http://www.ccas.ru/personal/karatsuba/alg.htm