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

Умножение Карацубы — метод быстрого умножения, позволяющий перемножать два $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)$. Используя тождество:

$(a+b)(c+d)=ac+(ad+bc)+bd$,

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

$(ax+b)(cx+d)=ac{x}^2+(ad+bc)x+bd=$

$=ac{x}^2+((a+b)(c+d)-ac-bd)x+bd$.

В последнем выражении участвуют три произведения $\left(\lceil \frac{n}{2}\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{array}{c}N=1111\cdot 10000+3333\\ M=5555\cdot 10000+7777\end{array}$

Раскрывая скобки, произведение $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