Processing math: 21%

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

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

M(n)=O(nlog23),log23=1,5849
 Этот подход открыл новое направление в вычислительной математике —теорию создания быстрых алгоритмов. Исторически это первый методбыстрого умножения, изобретенный А. А. Карацубой в 1960 году.

История


 Проблема оценки количества битовых операций, достаточного для вычисленияпроизведения двух n-значных чисел, или проблема роста функциисложности умножения M(n) при n+ является нетривиальнойпроблемой теории быстрых вычислений.
 Первые постановки задач о сложности вычислений принадлежатА. Н. Колмогорову, который в то же время подчёркивал, что этот циклработ находится под большим влиянием Норберта Винера и Клода Шеннона.
 Перемножение двух n-значных целых чисел обычным школьным методом«в столбик» сводится, по сути, к сложению n n-значныхчисел. Поэтому для сложности этого «школьного» или «наивного» методаимеем оценку сверху:

M(n)=O(n2).
 У Колмогорова была гипотеза, что нижняя оценка для M(n) при любомметоде умножения есть также величина порядка n2. На правдоподобность«гипотезы n2» указывал тот факт, что метод умножения «в столбик»известен не менее четырёх тысячелетий (например, этим методомпользовались шумеры), и если бы был более быстрый метод умножения, тоон, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацубанашёл новый метод умножения двух n-значных чисел с оценкойсложности

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

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


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


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

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

X=e0+2e1++2n1en1,
 где ej{0,1},j=0,1,,n1.
 Будем считать для простоты, что n=2m,m.Представляя 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}
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_2 — k-значные числа, находим:

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 не на два, а на большее количество слагаемых, томожно получать асимптотически лучшие оценки сложности вычисленияпроизведения (возведения в квадрат).
 Метод умножения Шёнхаге — Штрассена имеет меньшую асимптотическуюсложность, чем алгоритм Карацубы.