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

Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два 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,m1;n=2k. Представляя X в виде

X=X1+2kX2,
  где

X1=e0+2e1++2k1ek1
  и

X2=ek+2ek+1++2k1en1,
  находим:

X2=(X1+2kX2)2=X12+((X1+X2)2(X12+X22))2k+X222n.(1)
  Числа X1 и X2 являются k-значными. Число X1+X2 может иметь k+1 знаков. В этом случае представим его в виде 2X3+X4, где X3 есть k-значное число, X4 — однозначное число. Тогда

(X1+X2)2=4X32+4X3X4+X42.
  Обозначим φ(n) — количество операций, достаточное для возведения n-значного числа в квадрат по формуле (1). Из (1) следует, что для φ(n) справедливо неравенство:

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

φ(n21),φ(n22),,φ(n2m+1)
  и принимая во внимание, что

φ(n2m)=φ(1)=1,
  получаем

φ(n)3(3φ(n22)+cn21)+cn=32φ(n22)+3c(n21)+cn

3mφ(n2m)+3m1c(n2m+1)+3m2c(n2m+2)++3c(n21)+cn=
=3m+cn((32)m1+(32)m2++(32)+1)=
=3m+2cn((32)m1)<3m(2c+1)=(2c+1)nlog23.

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

φ(n)<(2c+1)nlog23,log23=1,5849
  Если же n не является степенью двух, то определяя целое число m неравенствами $2^{m-1}
en==e2m1=0.
  Все остальные рассуждения остаются в силе, и для φ(n) получается такая же верхняя оценка по порядку величины n.

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


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

(a+bx)(c+dx)=ac+((a+b)(c+d)acbd)x+bdx2.
  Пусть, как и раньше n=2m, n=2k, A и B — два n-значных числа. Представляя A и B в виде

A=A1+2kA2,B=B1+2kB2,
  где A1,A2,B1,B2 — k-значные числа, находим:

AB=A1B1+2k((A1+A2)(B1+B2)(A1B1+A2B2))+2nA2B2.(3)
  Таким образом, в этом случае формула (1) заменяется формулой (3). Если теперь обозначить символом φ(n) количество операций, достаточное для умножения двух n-значных чисел по формуле (3), то для φ(n) выполняется неравенство (2), и, следовательно, справедливо неравенство:

φ(n)<(2c+1)nlog23,log23=1,5849

Замечания


 Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до n знаков функции y=x2 в некоторой точке x=x1.
 Если разбивать X не на два, а на большее количество слагаемых, то можно получать асимптотически лучшие оценки сложности вычисления произведения (возведения в квадрат).
 Метод умножения Шёнхаге — Штрассена имеет меньшую асимптотическую сложность, чем алгоритм Карацубы.