Умножение Карацубы

Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа со сложностью вычисления:

$M(n)=O(n^{\log_23}),\quad\log_23=1{,}5849\ldots$

Этот подход открыл новое направление в вычислительной математике ^[1][2].

История

Проблема оценки количества битовых операций, достаточного для вычисления произведения двух n-значных чисел, или проблема роста функции сложности умножения $M(n)$ при $n\to+\infty$ является нетривиальной проблемой теории быстрых вычислений.

Перемножение двух n-значных целых чисел обычным школьным методом «в столбик» сводится, по сути, к сложению n n-значных чисел. Поэтому для сложности этого «школьного» или «наивного» метода имеем оценку сверху:

$M(n)=O(n^2).$

В 1956 году А. Н. Колмогоров сформулировал гипотезу, что нижняя оценка для $M(n)$ при любом методе умножения есть также величина порядка $n^2$ (так называемая «гипотеза $n^2$» Колмогорова). На правдоподобность гипотезы $n^2$ указывал тот факт, что метод умножения «в столбик» известен не менее четырёх тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацуба^[3][4][5][6] нашёл новый метод умножения двух n-значных чисел с оценкой сложности

$M(n)=O(n^{\log_23})$

и тем самым опроверг «гипотезу $n^2$».

Впоследствии метод Карацубы был обобщён до парадигмы «разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения (англ.), двоичный поиск, метод бисекции и др.

Ниже представлены два варианта (из многих) умножения Карацубы.

Описание метода

Первый вариант

Этот вариант основан на формуле

$(a+bx)^2=a^2+((a+b)^2-a^2-b^2)x+b^2x^2.$

Поскольку $4ab=(a+b)^2-(a-b)^2$, то умножение двух чисел $a$ и $b$ эквивалентно по сложности выполнения возведению в квадрат.

Пусть $X$ есть $n$-значное число, то есть

$X=e_0+2e_1+\ldots+2^{n-1}e_{n-1},$

где $e_j\in{0,\;1},\;j=0,\;1,\;\ldots,\;n-1$.

Будем считать для простоты, что $n=2^m,\;m\geqslant 1;\;n=2k$. Представляя $X$ в виде

$X=X_1+2^kX_2,$

где

$X_1=e_0+2e_1+\ldots+2^{k-1}e_{k-1}$

и

$X_2=e_k+2e_{k+1}+\ldots+2^{k-1}e_{n-1},$

находим:

$X^2=(X_1+2^kX_2)^2=X_1^2+((X_1+X_2)^2-(X_1^2+X_2^2))2^k+X_2^22^n.\qquad(1)$

Числа $X_1$ и $X_2$ являются $k$-значными. Число $X_1+X_2$ может иметь $k+1$ знаков. В этом случае представим его в виде $2X_3+X_4$, где $X_3$ есть $k$-значное число, $X_4$ — однозначное число. Тогда

$(X_1+X_2)^2=4X_3^2+4X_3X_4+X_4^2.$

Обозначим $\varphi(n)$ — количество операций, достаточное для возведения $n$-значного числа в квадрат по формуле (1). Из (1) следует, что для $\varphi(n)$ справедливо неравенство:

$\varphi(n)\leqslant 3\varphi(n2^{-1})+cn,\qquad(2)$

где $c>0$ есть абсолютная константа. Действительно, правая часть (1) содержит сумму трёх квадратов $k$-значных чисел, $k=n2^{-1}$, которые для своего вычисления требуют $3\varphi(m)=3\varphi(n2^{-1})$ операций. Все остальные вычисления в правой части (1), а именно умножение на $4,\;2^k,\;2^n$, пять сложений и одно вычитание не более чем $2n$-значных чисел требуют по порядку не более $n$ операций. Отсюда следует (2). Применяя (2) последовательно к

$\varphi(n2^{-1}),\;\varphi(n2^{-2}),\;\ldots,\;\varphi(n2^{-m+1})$

и принимая во внимание, что

$\varphi(n2^{-m})=\varphi(1)=1,$

получаем

$\varphi(n)\leqslant 3(3\varphi(n2^{-2})+cn2^{-1})+cn=3^2\varphi(n2^{-2})+3c(n2^{-1})+cn\leqslant\ldots\leqslant$

$\leqslant 3^m\varphi(n2^{-m})+3^{m-1}c(n2^{-m+1})+3^{m-2}c(n2^{-m+2})+\ldots+3c(n2^{-1})+cn=$

$=3^m+cn\left(\left(\frac{3}{2}\right)^{m-1}+\left(\frac{3}{2}\right)^{m-2}+\ldots+\left(\frac{3}{2}\right)+1\right)=$

$=3^m+2cn\left(\left(\frac{3}{2}\right)^m-1\right)<3^m(2c+1)=(2c+1)n^{\log_23}.$

Тем самым для количества $\varphi(n)$ операций, достаточного для возведения $n$-значного числа в квадрат по формуле (1) выполняется оценка:

$\varphi(n)<(2c+1)n^{\log_23},\quad \log_23=1{,}5849\ldots$

Если же $n$ не является степенью двух, то определяя целое число $m$ неравенствами $2^{m-1}<n\leqslant 2^m$, представим $X$ как $2^m$-значное число, то есть полагаем последние $2^m-n$ знаков равными нулю:

$e_n=\ldots=e_{2^m-1}=0.$

Все остальные рассуждения остаются в силе и для $\varphi(n)$ получается такая же верхняя оценка по порядку величины $n$.

Второй вариант

Это непосредственное умножение двух $n$-значных чисел, основанное на формуле

$(a+bx)(c+dx)=ac+((a+b)(c+d)-ac-bd)x+bdx^2.$

Пусть, как и раньше $n=2^m$, $n=2k$, $A$ и $B$ — два $n$-значных числа. Представляя $A$ и $B$ в виде

$A=A_1+2^kA_2,\quad B=B_1+2^kB_2,$

где $A_1,\;A_2,\;B_1,\;B_2$ — $k$-значные числа, находим:

$AB=A_1B_1+2^k((A_1+A_2)(B_1+B_2)-(A_1B_1+A_2B_2))+2^nA_2B_2.\qquad(3)$

Таким образом, в этом случае формула (1) заменяется формулой (3). Если теперь обозначить символом $\varphi(n)$ количество операций, достаточное для умножения двух $n$-значных чисел по формуле (3), то для $\varphi(n)$ выполняется неравенство (2), и, следовательно, справедливо неравенство:

$\varphi(n)<(2c+1)n^{\log_23},\quad\log_23=1{,}5849\ldots$

Замечания

Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до $n$ знаков функции $y=x^2$ в некоторой точке $x=x_1$.

Если разбивать $X$ не на два, а на большее количество слагаемых, то можно получать асимптотически лучшие оценки сложности вычисления произведения (возведения в квадрат).

Метод умножения Шёнхаге — Штрассена имеет меньшую асимптотическую сложность, чем алгоритм Карацубы.

См. также

• Сложность вычисления (битовая)
• АГС метод Гаусса
• Метод БВЕ
• Быстрые алгоритмы
• Метод умножения Шёнхаге — Штрассена
• Алгоритм Фюрера

Примечания

1. ↑ Карацуба Е. А. Быстрые алгоритмы и метод БВЕ, 2008.
2. ↑ Алексеев В. Б. От метода Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Тр. МИАН. — 1997. — Т. 218. — С. 20–27.
3. ↑ Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145. — № 2.
4. ↑ Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (нем.) // Elektronische Informationsverarbeitung und Kybernetik. — 1975. — Т. 11.
5. ↑ Карацуба А. А. Сложность вычислений // Тр. МИАН. — 1995. — Т. 211. — С. 186–202.
6. ↑ Кнут Д. Искусство программирования. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 0-201-89684-2

Ссылки

• http://212.cmc-msu.ru/files/kniga.html
• http://gersoo.free.fr/docs/karat/kar.html
• http://numbers.computation.free.fr/Constants/Algorithms/representation.html
• 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/
• 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
• http://habrahabr.ru/blogs/algorithm/124258/