Умножение Карацубы | это... Что такое Умножение Карацубы? (original) (raw)

Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два _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 , то умножение двух чисел и эквивалентно по сложности выполнения возведению в квадрат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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)$ количество операций, достаточное для умножения двух -значных чисел по формуле (3), то для $\varphi(n)$ выполняется неравенство (2), и, следовательно, справедливо неравенство:

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

Замечания

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

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

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

См. также

Примечания

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