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

В 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 x=10^{k}}$ вместо ${\displaystyle x=2^{k}}$. Цветовая разметка цифр не связана с предыдущим разделом, а обозначает лишь, из какого числа вычленяется та или иная часть.

Вычислим ${\displaystyle {\color {red}1213}\cdot {\color {blue}2311}}$:

• заметим, что ${\displaystyle {\color {red}12}+{\color {red}13}=25,\ {\color {blue}23}+{\color {blue}11}=34}$ и вычислим ${\displaystyle {\color {darkorange}25}\cdot {\color {magenta}34}}$:
  • заметим, что ${\displaystyle {\color {darkorange}2}+{\color {darkorange}5}=7,\ {\color {magenta}3}+{\color {magenta}4}=7}$ и вычислим ${\displaystyle 7\cdot 7=49}$
  • вычислим ${\displaystyle {\color {darkorange}2}\cdot {\color {magenta}3}=6}$
  • вычислим ${\displaystyle {\color {darkorange}5}\cdot {\color {magenta}4}=20}$
  • складывая результаты, получим, что ${\displaystyle {\color {darkorange}25}\cdot {\color {magenta}34}=6\cdot 10^{2}+(49-6-20)\cdot 10+20=850}$
• вычислим ${\displaystyle {\color {red}12}\cdot {\color {blue}23}}$ как ${\displaystyle {\color {darkorange}12}\cdot {\color {magenta}23}}$:
  • заметим, что ${\displaystyle {\color {darkorange}1}+{\color {darkorange}2}=3,\ {\color {magenta}2}+{\color {magenta}3}=5}$ и вычислим ${\displaystyle 3\cdot 5=15}$
  • вычислим ${\displaystyle {\color {darkorange}1}\cdot {\color {magenta}2}=2}$
  • вычислим ${\displaystyle {\color {darkorange}2}\cdot {\color {magenta}3}=6}$
  • складывая результаты, получим, что ${\displaystyle {\color {darkorange}12}\cdot {\color {magenta}23}=2\cdot 10^{2}+(15-2-6)\cdot 10+6=276}$
• вычислим ${\displaystyle {\color {red}13}\cdot {\color {blue}11}}$ как ${\displaystyle {\color {darkorange}13}\cdot {\color {magenta}11}}$:
  • заметим, что ${\displaystyle {\color {darkorange}1}+{\color {darkorange}3}=4,\ {\color {magenta}1}+{\color {magenta}1}=2}$ и вычислим ${\displaystyle 4\cdot 2=8}$
  • вычислим ${\displaystyle {\color {darkorange}1}\cdot {\color {magenta}1}=1}$
  • вычислим ${\displaystyle {\color {darkorange}3}\cdot {\color {magenta}1}=3}$
  • складывая результаты, получим, что ${\displaystyle {\color {darkorange}13}\cdot {\color {magenta}11}=1\cdot 10^{2}+(8-1-3)\cdot 10+3=143}$
• складывая результаты, получим, что ${\displaystyle {\color {red}1213}\cdot {\color {blue}2311}=276\cdot 10^{4}+(850-276-143)\cdot 10^{2}+143=2803243}$