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

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

!См., например, [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,

при fceN, где u,w — вещественные числа, причем и^О, w^l, a ip — неотрицательная функция, определенная для всех п е N+. Тогда при всех п е N⁺ выполняется неравенство

(и, если п = 1, /Тп-П Пое.п (²⁷.³)

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

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

|"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+ и

Я2Ц

и, если к = 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+ и

/<2Ц

и, если к = 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)