А ОЛ (В ОЛ (АВ О

Добавление нулей

Ряд алгоритмов целочисленной арифметики и теории матриц оказы­вается достаточным (без нанесения сколь-либо существенного ущер­ба идее алгоритма и его качеству) описать для случая, когда размер

!См., например, [4].

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

входа есть число вида 2^к. При использовании стратегии «разделяй и властвуй» это облегчает и описание алгоритма, и анализ его слож­ности. С теоретической точки зрения для задачи умножения двух це­лых чисел а и Ъ мы можем предполагать, что битовая длина каждого из данных чисел равна 2^к, где

fc = max{[log₂ А(а)1, flog₂A(b)l}, (27.1)

так как всегда возможно добавить спереди любого из данных чисел некоторое количество нулей. Если речь идет об умножении квадрат­ных матриц А и В произвольного порядка п, то мы можем добавить к матрицам несколько нулевых строк и столбцов так, чтобы сделать их порядки равными 2^Г1о&п1:

A0 B0 AB0 00 00 00

О 00 00 О (27.2)

(нулями обозначены нулевые блоки соответствующего размера). Несмотря на переход от начальных данных к более громоздким, неко­торые из алгоритмов, основанных на стратегии «разделяй и власт­вуй» и использующих этот переход, имеют существенно меньшую сложность, чем наивные алгоритмы.

Предложение 27.1.Пусть вещественная функция f натурального аргумента такова, что /(п) =/(2^г1о&"1) для всех neN+ и

/(2^fc)^

u, если k=0,

wf(2^k-1) +ϕ(2^k), если k >0,

Доказательство. Легко видеть, что

|"log₂|"|]]=riog₂nl-l. (27.4)

В самом деле, если 2^к-^г < п s= 2^к, к > 1, то 2^к-² < Г|1 s= 2^к-^х, т. е. ес­ли [log₂nl=fc, то riogJ|ll =к-1. Для случая n = 2^rlo&^nl неравен­ство (27.3) выполнено по условию, для остальных случаев используем равенства /(n) = /(2^rlo&^nl), /ГГ-11 = /(г¹"¹⁰^¹""/²"¹"¹) = /(2^rlog2^п_|-¹). □

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

Теорема 27.1.Пусть вещественная функция f натурального аргу­мента такова, что /(п) =/(2^г1о&"1) для всех neN+ и

и, если к = 0,

wf(2^fc-¹)+c(2^fc)^d, еслик>0,

при fc е N, где и,d ^ О, о О, w ^ 1. Тогда при рассмотрении f как функции, определенной для всех п е N+ выполняются оценки

(o(n^dlogn), если d = log₂w,

f(n) = \o{n^d), если d>log₂w,

[о(п^1о&^№), если d<log₂ мл

Доказательство следует из предложения 27.1 и теоремы 26.1. □

Подобно тому, как доказательство теоремы 26.1 было преобразо­вано в доказательство теоремы 26.2, из приведенного выше доказа­тельства мы можем получить доказательство следующей теоремы

Теорема 27.2.Пусть вещественная функция f натурального аргу­мента такова, что /(п) =/(2^г1о&"1) для всех neN+ и

и, если к = 0,

wf(2^fc-¹)+c(2^fc)^d, еслик>0,

где и, d ^ 0, о 0, w^ 1. Тогда для функции f{n), при рассмотрении ее как функции, определенной для всех п е N+ выполнено

fn(n^dlogn), если d=log₂w,

f{n) = I П(п^1о& ^w), если d > log₂ w,

[n(n^d), если d<log₂w.

Перейдем к примерам.

Пример27.1 (умножение Карацубы).Пусть а и Ъ — целые по­ложительные числа битовой длины т = 2^к. Положив Z = 2^fc-1, можем записать

a = e2^l+f, b = g2^l+h,

где e,f,g,h — целые числа битовой длины Z. А.А.Карацубе принад­лежит замечательное наблюдение, позволяющее вычислить произве­дение ab, выполнив всего три умножения чисел половинной длины, несколько сдвигов (домножений на 2^т и 2¹) и несколько аддитивных операций над числами битовой длины s= 2т:

аЪ = eg2²¹ + ((е + /) (g + К) - eg - fh)2^l + fh, (27.5)

§ 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 этой статьи.

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

использовании простейшего алгоритма, основанного на определении произведения матриц):

Х_г = (А_и + А₂₂) (В_п + Ваг), *5 = (Ац + А₁₂)В₂₂,
Х₂ = (А₂₁ + А₂₂)В_1Ъ Х₆ = (А₂₁ - А_п) (В_п + В₁₂),

Х₃ = А_П(В₁₂ -В₂₂), Х₇ = (А₁₂ - А₂₂)(В₂₁ + В₂₂),

Х₄=А₂₂(В₂₁-В_п), далее используются только аддитивные операции:

С_п=Х₁+Х₄-Х₅+Х₇, c₁₂ = x₃+x_s,

с₂₁ = х₂ + х₄, с₂₂ = х₁ + х₃-х₂ + х₆.

В правильности этого можно убедиться прямой проверкой.

Равенство п = 2^к создает возможность для рекурсивного примене­ния алгоритма. Алгоритм Штрассена будем обозначать начальными буквами St фамилии его автора.

В приведенных формулах использовано восемнадцать сложений матриц порядка Z. Сложение двух матриц порядка Z требует I² сло­жений чисел. В предположении, что n = 2^fc,fceN, имеем для общего числа операций—сложений и умножений чисел:

1, если п = 1,

ГпЛ ГпЛ² (27.12)

7r_St(JJ+18(Jj , еслип>1.

Если п е N+ произвольно, то вначале к матрицам А и В добавля­ются нулевые строки и столбцы (см. (27.2)) так, чтобы порядки мат­риц стали равными 2^Г1о&п1, а затем применяется описанный рекур­сивный алгоритм. Рассматривая равенство (27.12) как систему двух неравенств со знаками ^ и ^ и применяя теоремы 27.1 и 27.2, полу­чаем следующий результат.

Сложность Г_а(п) по числу арифметических операций алгоритма Штрассена перемножения двух числовых матриц порядка п допускает оценку r_st(n) = e(n^l0&⁷), в то время как алгоритм, непосредственно следующий из определения произведения матриц, имеет сложность в(п³) (при этом log₂ 7 = 2,81...).

Что касается булевых матриц, то алгоритм Штрассена не может быть непосредственно применен для их умножения по той, напри­мер, причине, что этим алгоритмом используется вычитание, для ко­торого нет аналога в булевой арифметике. Но матрицы А и В по­рядка п, состоящие из нулей и единиц, можно перемножить как

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

целочисленные. Каждый элемент такого произведения не превосхо­дит n, он равен нулю, если и только если соответствующий эле­мент произведения булевых матриц равен нулю. Для того, чтобы в процессе применения алгоритма Штрассена к целочисленным мат­рицам не возникало больших промежуточных значений, здесь мож­но все вычисления проводить по модулю n + 1, т. е. проводить вы­числения не в кольце Z, а в кольце Z_n+1. Если M{n)—некото­рая верхняя граница для числа битовых операций, затрачиваемых при выполнении одной операции сложения, вычитания или умноже­ния в Z_n+1, то сложность модифицированного таким способом ал­горитма Штрассена будет допускать оценку O{n^ъ^⁷M{n)). Наивное умножение в Z_n+1 дает M(n) = O(log² n). Таким образом, M{n) рас­тет очень медленно в сравнении с остальными затратами. Так как log₂ 7 = 2,81..., мы можем использовать для сложности алгоритма Штрассена, модифицированного на булев случай, например, оценку O(n²'⁸²) или оценку O(n^1о&⁷), —смысл «O мягкого» объяснялся в кон­це § 22.

Применение алгоритма Штрассена и арифметики по модулю n + 1 дает алгоритм умножения двух булевых матриц порядка n, битовая сложность которого допускает оценки O{n^ъ^⁷) и O(n²'⁸²).

Мы ограничились рассмотрением применения стратегии «разде­ляй и властвуй» для случая, когда в результате этапа разделения воз­никают две задачи, и каждый из размеров входа примерно вдвое меньше изначального размера. Иногда разделение приводит к трем и более задачам.

В 1963 г. А.Л.Тоом обобщил идею умножения Карацубы¹. Пусть s — большее единицы целое. Предполагая, что битовая длина m каж­дого из сомножителей имеет вид s^k, k е N, последовательность дво­ичных цифр каждого из сомножителей можно разбить на s групп по s^k-1 цифр. Тоом показал, что умножение исходных чисел сводится к 2s - 1 умножениям чисел битовой длины s^k-1 (в умножении Кара­цубы s = 2, 2s - 1 = 3), остальные затраты—сложения, сдвиги—будут ограничены функцией cm, где c — зависящая от выбора s константа. Здесь этап разделения приводит к 2s - 1 задачам. Для умножения То-ома (TM) неравенство

T^(m)^ _sГmЛ (²⁷.¹³)

См. [36], [4].

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

выполненное в случае m = s^k, fceN, и равенство

r«(m) = rW(s'l⁰&ml)_J

выполненное при произвольном meN⁺, приводят к оценке Т^(т) = = 0(m^logs(2s-^i:)) для битовой сложности алгоритма, использующего разбиение на s частей. Может быть также показано, что

r^(s)(m) = e(m^log»^(2s-¹⁾). (27.14)

Очевидно,

log_s(2s - 1) = log_s 2s(l - ^) = 1 + log_s 2 + log_s(l - ^) •

Отсюда

limlog,(2s-l) = l.

Это означает, что для любого е > О можно найти целое s ^ 2 такое, что умножение Тоома с разделением на s частей (битовая длина числа предполагается равной s^k, fceN) будет иметь битовую сложность, до­пускающую оценку 6(т¹⁺⁵) при некотором 5 таком, что 0 < 5 ^ е; ра­зумеется, для битовой сложности этого алгоритма справедлива оцен­ка 0(.т¹⁺П.

Скажем коротко об основной идее алгоритма Тоома, приводящей к неравенству (27.13). Если, как предполагалось, битовая длина каж­дого из сомножителей а,Ъ есть s^k, fceN, то последовательность дво­ичных цифр каждого из сомножителей а, Ъ можно разбить на s групп по s^-1 цифр:

а₃-ъ ■■■> ai> ^ао> b_s-₁, ...,Ь_г,Ъ₀. Сами сомножители а, Ъ суть значения полиномов

А(х) = а_-х"-¹ + ...+_а1х + а₀, В(х) = Ь_-х*^-1 + ... + Ъ_гх + Ъ₀

в точке х₀ = 2^s*^-1. Полином С(х), равный произведению А(х)В(х), есть полином степени не выше чем 2s - 2 (мы не утверждаем, что эта степень равна 2s - 2, так как возможно, что к изначально заданным целочисленным сомножителям спереди дописывались нули), и доста­точно знать значения С (х) в 2s- 1 точках (узлах интерполяции) для того, чтобы затем, например, с помощью интерполяционной форму­лы Лагранжа найти значение

СС2**-¹), (27.15)

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

равное ab. Тоом показал, что если в качестве узлов интерполяции x_ъ x₂,..., x_2s-i взять числа

-(s-l),-(s-2),...,-l,0,1, ...,s-2,s-l,

рекурсивно с помощью рассматриваемого алгоритма найти

A(x_i\ B{xi), C{x_i)=A{x_i)B{x_i), i = l,2,...,2s-l,

и затем, пользуясь интерполяционной формулой Лагранжа, найти значение (27.15), то это приведет к (27.13), (27.14). Такое использова­ние интерполяции заключает в себе требуемое обобщение алгоритма Карацубы.

В 1972 г. Шенхаге и Штрассен, основываясь на идее Тоома исполь­зования интерполяции полиномов в алгоритмах умножения целых чисел, получили алгоритм умножения, битовая сложность которого допускает оценку O{m log m log log m), мы уже упоминали этот алго­ритм в §21. Функция m log m log log m растет медленнее, чем m¹⁺⁵ при любом 5 > 0. Улучшение достигнуто за счет привлечения интер­поляции специального вида — так называемого быстрого преобразо­вания Фурье^г. До настоящего времени результат Шенхаге—Штрассе-на остается рекордным. Шенхаге на основе этого алгоритма умноже­ния предложил алгоритм² нахождения нод(a₀,a_г), сложность кото­рого допускает оценку O{m log² m log log m), где m — битовая длина большего числа a₀ (в примере 21.2 было показано, что алгоритм Ев­клида имеет сложность Θ(m²)).

Необходимо сказать, что преимущества по времени выполнения рассмотренных алгоритмов перед наивным умножением и алгорит­мом Евклида проявляются лишь при очень больших значениях m.

С умножением матриц положение таково, что обобщения алгорит­ма Штрассена в духе обобщения, предложенного Тоомом для алгорит­ма Карацубы, до сих пор не найдено. Используя другие идеи, Д. Коп-персмит и С. Виноград в 1987 г. предложили алгоритм со сложностью O(n^2,376), где n—порядок перемножаемых квадратных матриц³. Этот результат остается рекордным по сей день. Существует ли для любо­го s > 0 алгоритм умножения матриц со сложностью O{n^2+е)—это открытый вопрос.

Об алгоритме Шенхаге—Штрассена см., например, [5, разд. 7.5]. См., например, [5, разд. 8.10]. См. [47].

Задачи