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

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

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

История

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

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

Алгоритм

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

Два $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$ каждое из них представляется в виде суммы двух чисел вдвое меньшей разрядности, одно из которых взято со сдвигом^[10]:

{\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}$ при умножении наивным методом.

Примечания

↑ На практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка сотен двоичных (десятков десятичных) разрядов, на числах меньшей длины алгоритм не даёт существенного преимущества из-за большего, чем в наивном алгоритме, числа требуемых сложений, вычитаний и сдвигов.
↑ С. А. Гриценко, Е. А. Карацуба, М. А. Королёв, И. С. Резвякова, Д. И. Толев, М. Е. Чанга. Научные достижения Анатолия Алексеевича Карацубы // Математика и информатика, 1, К 75-летию со дня рождения Анатолия Алексеевича Карацубы, Совр. пробл. матем., 16, МИАН, М., 2012, 7–30.
↑ Карацуба Е. А. Быстрые алгоритмы и метод БВЕ Архивная копия от 4 ноября 2012 на Wayback Machine, 2008.
↑ Алексеев В. Б. От метода Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Тр. МИАН. — 1997. — Т. 218. — С. 20–27.
↑ Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145, № 2.
↑ Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (нем.) // Elektronische Informationsverarbeitung und Kybernetik. — 1975. — Bd. 11.
↑ Карацуба А. А. Сложность вычислений // Тр. МИАН. — 1995. — Т. 211. — С. 186–202.
↑ Кнут Д. Искусство программирования. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 0-201-89684-2.
↑ А. Шень. Gauss multiplication trick? (рус.) // Математическое Просвещение. — 2019. — Т. 24. Архивировано 21 января 2022 года.
↑ Сдвигом называется умножение или деление числа на целую степень основания системы счисления, «дописывание нулей».

Ссылки

[1] На практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка сотен двоичных (десятков десятичных) разрядов, на числах меньшей длины алгоритм не даёт существенного преимущества из-за большего, чем в наивном алгоритме, числа требуемых сложений, вычитаний и сдвигов.

[2] С. А. Гриценко, Е. А. Карацуба, М. А. Королёв, И. С. Резвякова, Д. И. Толев, М. Е. Чанга. Научные достижения Анатолия Алексеевича Карацубы // Математика и информатика, 1, К 75-летию со дня рождения Анатолия Алексеевича Карацубы, Совр. пробл. матем., 16, МИАН, М., 2012, 7–30.

[3] Карацуба Е. А. Быстрые алгоритмы и метод БВЕ Архивная копия от 4 ноября 2012 на Wayback Machine, 2008.

[4] Алексеев В. Б. От метода Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Тр. МИАН. — 1997. — Т. 218. — С. 20–27.

[5] Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145, № 2.

[6] Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (нем.) // Elektronische Informationsverarbeitung und Kybernetik. — 1975. — Bd. 11.

[7] Карацуба А. А. Сложность вычислений // Тр. МИАН. — 1995. — Т. 211. — С. 186–202.

[8] Кнут Д. Искусство программирования. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 0-201-89684-2.

[9] А. Шень. Gauss multiplication trick? (рус.) // Математическое Просвещение. — 2019. — Т. 24. Архивировано 21 января 2022 года.

[10] Сдвигом называется умножение или деление числа на целую степень основания системы счисления, «дописывание нулей».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]