А ОЛ (В ОЛ (АВ О

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

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

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

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

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

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

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

A 0 B 0 AB 0 00 00 00

О 00 00 О (27.2)

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

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

/(2^fc)^

u, если k =0,

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

при fceN, где u,w — вещественные числа, причем и^О, w^l, a ip — неотрицательная функция, определенная для всех п е N+. Тогда при всех п е N⁺ выполняется неравенство (и, если п = 1, /Тп-П Пое.п ___________ (²⁷.³)

^_/gij^ +^(2nog2 n i)₎ если_п>1_

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

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

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

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

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

Я2Ц

и, если к = 0,

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

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

(o(n^d log n), если 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) для всех n eN+ и

/<2Ц

и, если к = 0,

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

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

fn(n^d log n), если 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 + h i,

где 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₂ m l, затем добавляем спереди каждого из а,Ъ некоторое ко­личество нулей так, чтобы битовая длина каждого из сомножителей стала равной 2^к, а после этого используем рекурсивный алгоритм, основанный на (27.5).

Мы можем применить теорему 27.1 (w = 3, d = 1), так как при произвольном m eN+ выполняется Г_км(т) = Г_км(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,

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

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

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

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

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. Рекуррентные соотношения и сложность алгоритмов

O (n ^1о&⁷),-смысл

целочисленные. Каждый элемент такого произведения не превосхо­дит 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} цифр. Тоом показал, что умножение исходных чисел сводится к 2 s - 1 умножениям чисел битовой длины s^{k -1} (в умножении Кара­цубы s = 2, 2 s - 1 = 3), остальные затраты—сложения, сдвиги—будут ограничены функцией cm, где c — зависящая от выбора s константа. Здесь этап разделения приводит к 2 s - 1 задачам. Для умножения То-ома (TM) неравенство

1, если m = 1, (2 s - 1) T ^ (—) + cm, если m > 1,

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

См. [36], [4].

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

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

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

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

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

Очевидно,

log _s (2 s - 1) = log _s 2 s (l - ^) = 1 + log _s 2 + log _s (l - ^) •

Отсюда

limlog,(2 s -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. Полином С(х), равный произведению А(х)В(х), есть полином степени не выше чем 2 s - 2 (мы не утверждаем, что эта степень равна 2 s - 2, так как возможно, что к изначально заданным целочисленным сомножителям спереди дописывались нули), и доста­точно знать значения С (х) в 2 s - 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].

Задачи

Дата добавления: 2014-01-11