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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

История[править | править вики-текст]

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

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

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

В 1956 году А. Н. Колмогоров сформулировал гипотезу, что нижняя оценка для M(n) при любом методе умножения есть также величина порядка n^2 (так называемая «гипотеза n^2» Колмогорова). На правдоподобность гипотезы n^2 указывал тот факт, что метод умножения «в столбик» известен не менее четырёх тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацуба[4][5][6][7] нашёл новый метод умножения двух 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(\tfrac{3}{2}\right)^{m-1}+\left(\tfrac{3}{2}\right)^{m-2}+\ldots+\left(\tfrac{3}{2}\right)+1\right)=
=3^m+2cn\left(\left(\tfrac{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+\Big((a+b)(c+d)-ac-bd\Big)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_2k-значные числа, находим:

AB=A_1B_1+2^k\Big((A_1+A_2)(B_1+B_2)-(A_1B_1+A_2B_2)\Big)+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. С. А. Гриценко, Е. А. Карацуба, М. А. Королëв, И. С. Резвякова, Д. И. Толев, М. Е. Чанга, Научные достижения Анатолия Алексеевича Карацубы // Математика и информатика, 1, К 75-летию со дня рождения Анатолия Алексеевича Карацубы, Совр. пробл. матем., 16, МИАН, М., 2012, 7–30.
  2. Карацуба Е. А. Быстрые алгоритмы и метод БВЕ, 2008.
  3. Алексеев В. Б. От метода Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Тр. МИАН. — 1997. — Т. 218. — С. 20–27.
  4. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145. — № 2.
  5. Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (нем.) // Elektronische Informationsverarbeitung und Kybernetik. — 1975. — Т. 11.
  6. Карацуба А. А. Сложность вычислений // Тр. МИАН. — 1995. — Т. 211. — С. 186–202.
  7. Кнут Д. Искусство программирования. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 0-201-89684-2.

Ссылки[править | править вики-текст]