§ 27. Добавление нулей 175

тогда как обычное раскрытие скобок в (e2^l + f)(g2^l + К) требует вы­полнения четырех таких умножения:

ab = eg2^2l + (eh + fg)2^l+fh. (27.6)

Мы видим, что формула (27.5) использует произведения eg, fh, (e + /)(g + h), а формула (27.6)—произведения eg,eh,fg,fh.

Небольшая проблема, которая выше была замаскирована слова­ми «половинная длина», состоит в том, что битовая длина любого из чисел e + f, g + h, входящей в произведение (е+ /)(# +ft), может оказаться равной Z +1, а не Z. Но если

e + f = e_x2^l+f_x, g + h = g₁2^l + hi,

где e₁,g₁ — однобитовые числа (0 или 1), то

(е + f)ig + K)= e_lg_l2²¹ + (e_xh_x + g₁/₁)2^l + f_xh_x. (27.7)

Произведение Л 7^ вычисляется рекурсивным обращением к алгорит­му, произведения e₁g₁,e₁h₁,g₁f₁, как и все сложения и сдвиги, тре­буют 0(1) операций.

Равенство (27.5) и предположение, что т = 2^к, приводят к рекур­сивному алгоритму Карацубы умножения целых положительных чи­сел (будем обозначать этот алгоритм буквами KM: первая из этих букв — начальная в фамилии автора алгоритма, вторая — в англий­ском слове multiplication —умножение). Предположение т = 2^к при­водит к следующему соотношению для битовой сложности умноже­ния Карацубы:

( 1, если т = 1,

ГтЛ (27.8)

ЗГ_КМ1 у I +ст, еслит>1,

где с — некоторая положительная константа.

Умножение Карацубы при произвольном входе a, b е N+ разме­ра т = шах{А(а), А(Ь)} предполагает, что сначала мы находим к = = [log₂ml, затем добавляем спереди каждого из а,Ъ некоторое ко­личество нулей так, чтобы битовая длина каждого из сомножителей стала равной 2^к, а после этого используем рекурсивный алгоритм, основанный на (27.5).

Мы можем применить теорему 27.1 (w = 3, d = 1), так как при произвольном meN+ выполняется Г_км(т) = Г_км(2^Г1о&^т1). Получаем

Г_км(т) = 0(т^1о&³), (27.9)

при этом log₂ 3 = 1,58...

176 Глава 6. Рекуррентные соотношения и сложность алгоритмов

Для m > 1 мы имеем

T_KM(m)>G(m), (27.10)

где функция G натурального аргумента такова, что G(m) = G(2ⁿ°^^m]) для всех m е N⁺ и

G(2^k) =

1, еслиk=0,

3G(2^k-1), если k >0,

откуда T_км(m) = П(m^1о&³) по предложению 27.2. Вместе с (27.9) это дает

T_км(m) = в(m^1о&³). (27.11)

При использовании m, равного максимальной из битовых длин двух данных чисел a, beN+ в качестве размера входа битовая сложность умножения Карацубы допускает оценку

T_км(m) = в(m^1о&³),

при том, что T_мм = 6(m²) — оценка битовой сложности наивного умножения^г.

Стратегия добавления нулей особенно характерна для исследова­ний, в которых главной целью служит преодоление некоторого слож-ностного барьера; последнее было и остается важным стимулом раз­вития теории сложности.

Пример 27.2. Алгоритм Штрассена умножения двух квадратных числовых матриц A и B порядка n, являющегося степенью двойки, основан на том, что если n = 2l и

A = [A₁₁ A 12Л =(B_U B 12Л

A 21 A₂> B B 21 B₂₂>

где все A_ij,B_ij — квадратные матрицы порядка l, то матрицу

C=AB= CC

можно получить, выполнив семь умножений квадратных матриц по­рядка l (при том, что потребовалось бы восемь таких умножений при

¹ История создания алгоритма Карацубы и публикации о нем в 1962 г. сообще­ния [15] увлекательно рассказана в статье [17] самого А. А. Карацубы; особенно богат яркими историческими деталями раздел 6 этой статьи.