(in English)

МЕТОД КАРАЦУБЫ «DIVIDE AND CONQUER» *

        Здесь представлены два равносильных варианта метода Карацубы «Divide and Conquer» («Binary Splitting»). Первый вариант основан на формуле

(a + bx)2 = a2 + ((a + b)2 – a2 – b2)x + b2x2,

а второй — на формуле

(a + bx)(c + dx) = ac + ((a + b)(c + d) – ac – bd)x + bdx2.

I.      Так как  4ab = (a + b)2 – (a – b)2 то умножение двух чисел  a  и  b  эквивалентно по сложности выполнения возведению в квадрат.

        Пусть  X — n -значное число, т. е.

X = ε0 + 2ε1 + ... + 2n–1εn–1,

где  εj = 0  или  1,   j = 0, 1, ..., n-1.  Будем считать для простоты, что  n = 2m,   m ≥ 1;   2k = n.  Представляя  X  в виде

X = X1 + 2kX2,

где

X1 = ε0 + 2ε1 + ... + 2k–1εk–1 ,
X2 = εk + 2εk+1 + ... + 2k–1εn–1 ,

находим

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 .
(2)

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

φ(n) ≤ 3φ(n2–1) + cn ,
(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) ≤ 3(φ(n2–1) + cn2–1) + cn = 32φ(n2–2) + 3cn2–1 + cn ≤ ... ≤
≤   3mφ(n2–m) + 3m–1c(n2–m+1) + 3m–2c(n2–m+2) + ... + 3 c(n2–1) + cn =
= 3m + cn((3/2)m–1 + (3/2)m–2 + … + (3/2) + 1) =
= 3m + 2cn((3/2)m – 1) < 3m (2c + 1) = (2c+1) nlog 23

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

φ(n) < (2c+1) nlog 23 ,   log 2 3 = 1,5849... .
(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  в виде

A = A1 + 2kA2 ,   B = B1 + 2kB2,

где  A1, A2, B1, B2 — k -значные числа, находим:

AB = A1B1 + 2k((A1 + A2)(B1 + B2) – (A1B1 + A2B2)) + 2nA2B2 .
(5)

Таким образом, в этом случае формула (1) заменяется формулой (5). Если теперь обозначить символом  φ(n)  количество операций, достаточное для умножения двух  n-значных чисел по формуле (5), то для  φ(n)  выполняется неравенство (3), и, следовательно, справедливо неравенство (4).

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

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

        Метод «Divide and Conquer» (его другие названия «Принцип Дихотомии», «Binary Splitting», и т. п.) является основополагающим и наиболее общим быстрым методом. На его основе построены сотни различных алгоритмов.



J



        Об истории создания метода: А. А. Карацуба «Сложность вычислений» Труды Матем. инст. им. Стеклова, т. 211, с. 169-183 (1995).

        О методе «Divide and Conquer» и его использовании можно также посмотреть на многочисленных WEB-страницах, например:

БЫСТРЫЕ АЛГОРИТМЫ И МЕТОД БВЕ


*) Если какие-нибудь математические символы или формулы Вами не видны, Вы можете скачать себе файл в формате: MS-Word (40 960 байтов);

© Екатерина Карацуба
Страница создана 14.09.2005.
Последняя редакция 30.06.2013.