ЧТО меньше п. Для полного числа сложений имеем

что при л > 20 также меньше, чем {п - 1) п.

Еще большее улучшение дает рекурсивное использование алгоритма Штрассена, основанное на разбиении блоков на более мелкие подблоки и использовании тех же самых уравнений. В этом случае число умножений равно

М{п) = 7 = iog. 7 п2,81

Число сложений вычисляется сложнее. Оно удовлетворяет рекурсии

Л( ) = 7Л() + .з(-)\

Число сложений больше числа умножений, но также растет как При достаточно больших п это число меньше числа сложений, необходимых в прямом методе вычисления. При п = 1024 число необходимых в алгоритме сложений примерно равно числу стоже-ний прямого метода вычислений, но число умножений равно примерно одной четверти от числа умножений прямого метода вычисления произведения матриц раз.черности 1024.

10.7. Рекурсивный алгоритм Евклида

Стратегия дублирования позволяет ускорить алгоритм Евклида и построить алгорит.м, сложность которого имеет порядок и log п. Основные вычисления в алгоритме Евклида описываются уравнениями

о 1

.1 -e i(Jt)j

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

Имеется, однако, несколько деталей, о которых следует позаботиться. Первая трудность состоит в том, что мы не знаем заранее число итераций, так что невозможно сказать, когда половина итераций завершена. Эту трудность можно исключить, прерывая вычисления в точке, в которой выполнена примерно половина итераций.

Другая трудность состоит в том, что (х) зависит от А<1 (х), и, в свою очередь. А (х) зависит от Q-l (х). Следовательно, заранее не известны все участвующие в вычислении А ) (,х) его делители. При разбиении на группы необходимо позаботиться о том, чтобы ни один делитель не использовался раньше, чем он станет известным. Теорема 10.7.1 утверждает, что если разбиение алгоритма происходит в правильной точке, то структура обеих групп аналогична структуре исходной задачи.

Пусть матрица А*+ (х) факторизуется в виде

А<1 (х) = А(-+ч(х)А<1(х),

А<+11(х) = П

А1)(х)= П

- Q<)

1 -Q (x)

для некоторого фиксированного г. Первая группа уравнений состоит из г итераций, совпадающих с первыми г итерациями исходной задачи. Вторая группа содержит уравнения для г г -\-+ i....,R:

А< (дг) -П

Го I .1 -СЧд

когда многочлен f-) (х) обра-

и алгоритм останавливается, щается в нуль.

Q (.x) =

Эта группа вычислений, очевидно, имеет ту же форму, что и исходная задача.

Первая группа также имеет эту же структуру, но если для ее вычисления использовать тот же путь решения, то стратегия деления задачи не даст ожидаемого улучшения. Чтобы уменьшить сложность, надо унростить вычисление первой группы. Такое упрощение

Тогда частное Q (х) при делении многочлена f (х) на многочлен g (х) не зависит от к младших коэффициентов многочленов f (х) и g (х) и k младших коэффициентов многочленов / (х) и g (х) оказывают в.гияние только на те коэффициенты остатка г (х), индексы которых меньше, чем к -f deg / (х) - deg g(x). □

Согласно теореме 10.7.1, и многочлен-частное Q (х) и сегмент многочлена-остатка г (х) могут быть получены при усечении многочленов / (х) и g (х) до более коротких многочленов. Мы сейчас покажем, что отбрасывание сегмента многочлена-остатка г (х) не затрагивает некоторые последующие итерации алгоритма Евклида. На самом деле, если выбрать к разумно, то примерно половина итераций может быть вычислена без знания отброшенного сегмента остатка г (х).

Теорема 10.7.3. Пусть f (х) = / (х) х + Г (х) и g (х) =

= g (х) X* + g (х), где deg f (х) < ft и deg g (х) < ft. Пусть deg/(x) = n, deg g (х)< deg / (х), и пусть \ > {х) и А<) (х) обозначают матрицы из алгоритма Евклида, вычисленные соответственно для штрихованных и нештрихованных переменных. Тогда если deg g** (х) (п - ft)/2, то для каждого г выполняется равенство Ai (х) = А (х). {Иными словами, частные остаточных последовательностей, порождаемых в процессе выполнения алгоритма Евклида, для нештрихованных и штрихованных переменных совпадают по меньшей мере до тех пор, пока не будет достигнут остаток g** (х), степень которого меньше, чем половина степени f (х).)

Доказательство. Доказательство сводится к применению следствия 10.7.2 на каждом шаге итерации алгоритма Евклида для нештрихованных и штрихованных переменных при начальных условиях /( ) (X) = / (,v), gi ) (X) = g (X) и /( ) (X) = / (х), g<°i (х) = = g {х)-

Шаг 1. Следствие 10.7.2 можно применять на каждом шаге при условии, что выполняется неравенство ft < 2 deg g l (х) - - deg (х). Но нам дано, что

degg <>()>.

Мы покажем, что это условие эквивалентно нужному условию, свя.зывая степени штрихованных многочленов со степенями нештрихованных многочленов. Эти связи следуют из равенств

является источником значительной экономии числа вычислений и основывается на следующей теореме, описывающей условия, при которых возможно усечение делимого и делителя, не изменяющее частотного и остатка.

Теорема 10.7.1. Пусть два заданных многочлена / (х) и g (х), степени которых связаны соотношением deg g (х) < deg / (х), записаны в виде f (х) = / (X) X + / (х) и g{x) = g (х) х + g (x), где степени многочленов / (х) и g (х) меньше некоторого числа к, удовлетворяющего неравенству fe < 2 deg g (х) - deg f (x). Пусть алгоритм деления приводит соответственно к равенствам / (х) = = Q{x)g (х) + г{х) и Г W = С (X) g (х) -f г (X). Тогда

(i) Q (X) = Q (X),

(ii) г (х) = г (х) X* -f г (X), где степень многочлена г (х) меньше, чем к -f deg / (х) - deg g (х).

Доказательство. Утверждение теоремы является легко доказываемым следствием однозначности алгоритма деления. Начнем с равенства

/ (X) = Q (X) g (X) + / (X).

Тогда

/ (X) X* + / (X) = С (X) g (X) х + г (X) х -f Г (X),

/ (X) = Q (X) g (X) -i- f (X) X* + / (X) - q (X) g(x).

В силу однозначности алгоритма деления мы сможем заключить, что

Q (X) = q (X) и г (X) = (X) х -f Г ух) - Q (X) g- (X), если покажем, что

deg \г (X) х + Г (X) - Q (X) g (X) 1 < deg g (х). Но, используя условия теоремы, это легко проверить для каждого из трех многочленов, стоящих в левой части неравенства:

(i) deg Ir (х) х 1 < deg g (х) -f- ft = deg g (x),

(ii) deg / (x) < A - 1 < deg g (x), (iii) deg IQ (x) g (x) I < deg / (x) - deg g (x) -f ft =

= (deg / (x) - Й) - (deg g (X) - ft) + ft < deg g (x). Второе утверждение теоремы получится, если заметить, что из неравенств (ii) и (iii) следует, что степень многочлена f (х) - - Q (х) g (X) меньше, чем ft + deg / (х) - deg g (х). о

Следствие 10.7.2. Пусть целое число к удовлетворяет неравенству

ft < 2 deg g (X) - deg / (X).

364 Гл. 10. Быстрые алгоритмы, основанные на стратегии дублирования И

deg/( ) (х) = deg /< > (л:) - А,

deg я10) (х) = deggi ) (х) - ft.

Следовательно, поскольку многочлен-частное является одним и тем же многочленом в штрихованном и нештрихованном случаях, имеют место равенства

deg rM(x) = deg /)(x)-ft,

deg g<n (x) = deg gi>(x) ft.

Таким образом, нам дано, что

так как п = дится к условию

g<>(x)-ft> f<°> (X) > ft<2degg<0 (x)-dpg/<>(x),

(x). Это неравенство сразу сво-

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

Шаг 2. Согласно следствию 10.7.2, каждый многочлен-частное вычисляется правильно, если только предыдущий многочлен-частное был вычислен правильно и последний полученный многочлен-остаток содержит достаточное число правильных коэффициентов. Чтобы проверить последнее условие, опять воспользуемся следствием 10.7.2, заменив число ft числом

ftci = ft+ deg/(- (x) - deggt-4{x)

и полагая k> =- ft. Согласно следствию 10.7.2 к началу г-го шага итерации многочлен-остаток будет правильно вычислен за исклю чением, возможно, младших ft членов, что согласно тому же ,. следствию не влияет на вычисление многочлена-частного при условии, что fti) 2 deg g(> (х) - deg / > (х). Тот факт, что это . неравенство выполняется, проверяется следующим образом:

ft ) - 2 deg(х) -f degf<-> (x) = ft -f deg f<-4 (x) - deg gC- (x) -

- 2 deg gn {X) + deg /М (x) = ft -f deg/i-ч (x) - 2 с

(x)<

< ft + я - 2 (

I = 0,

где использованы неравенства deg п (x) <; я и

deg gC) (X) = deg g<> (X) + ft < . Таким образом,

ftci <2degg<0 (x)-deg/<) (x)

Рис. 10.7. Процедура ЕвкАлг.

и, следовательно, на г-м шаге итерации многочлен-частное не зависит от неизвестных коэффициентов. Это завершает доказательство теоре.мы. □

словие deg 1(ж) > (я - fe)/2 теоремы для нештрихо-ванных переменных можно переписать в виде deg g (х) > (л + + й)/2 , Эквивалентность этих условий используется в формулировке рекурсивной процедуры.

Разбиение алгоритма Евклида пополам показано на диаграмме на рис. 10.7. В основной точке ветвления алгоритма выносится ре-