Здесь представлены два равносильных варианта метода Карацубы «Divide and Conquer» («Binary Splitting»). Первый вариант основан на формуле
а второй — на формуле
I. Так как 4ab = (a + b)2 – (a – b)2, то умножение двух чисел a и b эквивалентно по сложности выполнения возведению в квадрат.
Пусть X — n -значное число, т. е.
где εj = 0 или 1, j = 0, 1, ..., n-1. Будем считать для простоты, что n = 2m, m ≥ 1; 2k = n. Представляя X в виде
где
находим
| (1) |
Числа X1 и X2 являются k -значными. Число X1 + X2 может быть k+1 -значным. В этом случае представим его в виде 2X3 + X4, где X3 есть k -значное число, X4 — однозначное число. Тогда
| (2) |
Обозначим через φ(n) количество операций, достаточное для возведения n -значного числа в квадрат по формуле (1). Из (1) следует, что для φ(n) справедливо неравенство
| (3) |
где c > 0 — абсолютная постоянная. Действительно, принимая во внимание (2), правая часть (1) содержит сумму трёх квадратов k -значных чисел, k = n2–1, которые для своего вычисления требуют 3φ(k) = 3φ(n2–1) операций. Все остальные вычисления в правой части (1), а именно умножение на 4, 2k, 2n, пять сложений и одно вычитание не более чем 2n -значных чисел требуют по порядку не более  :n операций. Отсюда следует (3). Применяя (3) последовательно к φ(n2–1), φ(n2–2) , ... , φ(n2–m+1) и замечая, что φ(n2–m) = φ(1) =1, получаем
Тем самым для количества φ(n) операций, достаточного для возведения n -значного числа в квадрат по формуле (1) выполняется оценка
| (4) |
Если же n не является степенью двух, то определяя целое число m неравенствами 2m–1 < n ≤ 2m, представим X как 2m -значное число, т. е. полагаем последние 2m–n знаков равными нулю: εn = ... = ε2m–1 = 0. Все остальные рассуждения остаются в силе и для φ(n) получается такая же верхняя оценка по порядку величины n.
II. Второй способ представлет собой непосредственное умножение двух n -значных чисел. Пусть, как и раньше n = 2m, 2k = n; A и B — два n -значных числа. Представляя A и B в виде
где A1, A2, B1, B2 — k -значные числа, находим:
| (5) |
Таким образом, в этом случае формула (1) заменяется формулой (5). Если теперь обозначить символом φ(n) количество операций, достаточное для умножения двух n-значных чисел по формуле (5), то для φ(n) выполняется неравенство (3), и, следовательно, справедливо неравенство (4).
Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до n знаков функции y = x2 в некоторой точке x = x1.
Если разбивать X не на два, а на большее количество слагаемых, то можно получать асимптотически лучшие оценки сложности вычисления произведения (возведения в квадрат).
Метод «Divide and Conquer» (его другие названия «Принцип Дихотомии», «Binary Splitting», и т. п.) является основополагающим и наиболее общим быстрым методом. На его основе построены сотни различных алгоритмов.
Об истории создания метода: А. А. Карацуба «Сложность вычислений» Труды Матем. инст. им. Стеклова, т. 211, с. 169-183 (1995).
О методе «Divide and Conquer» и его использовании можно также посмотреть на многочисленных WEB-страницах, например: