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

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

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

История

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

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

Алгоритм

Сравнение алгоритма Карацубы и умножения в столбик. Внизу схематически показано дерево рекурсивных вызовов алгоритма для всё меньших и меньших чисел. Количество вершин на последнем его уровне соответствует количеству элементарных умножений. Видно, что у алгоритма Карацубы ширина дерева растёт значительно медленнее.

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

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

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

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

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

$={\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}$.

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

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

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

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

Примеры

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

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

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

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

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

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

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

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