Умножение Карацубы - NiNa.Az

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

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

История

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

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

Алгоритм

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

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

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

Примечания

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. Сдвигом называется умножение или деление числа на целую степень основания системы счисления, «дописывание нулей».

Ссылки

• http://212.cmc-msu.ru/files/kniga.html
• http://numbers.computation.free.fr/Constants/Algorithms/representation.html
• http://www-2.cs.cmu.edu/~cburch/251/karat/
• http://www.cs.pitt.edu/~kirk/cs1501/animations/
• http://www.ccas.ru/personal/karatsuba/divcru.htm
• http://www.ccas.ru/personal/karatsuba/alg.htm