Главная Промышленная автоматика.

По предположению индукции и в силу (8.24)

aoAt;+, + +1 = О; -, - •

Так как Cj-i-qai=ai+i в силу строки 4, то лемма доказана. □

Заметим, что лемма 8.4 даже не зависит от способа вычисления q в строке 3, хотя строка 3 существенна, чтобы гарантировать, что алгоритм 8.6 действительно вычисляет НОД(ао, Ci). Суммируем эти замечания в следующей теореме.

Теорема 8.16. Алгоритм 8.6 вычисляет НОД(ао, Ci) и такие числа X и у, что а»х+а1г/=НОД(ао, Ci).

Доказательство. Элементарное упражнение на применение леммы 8.4. □

Введем некоторые обозначения, которые понадобятся нам в следующем разделе.

Определение. Пусть а» и Ci- целые числа и Со, Oi, . . ., а*-соответствующая последовательность остатков. Пустьqi=\ Ui-Jai J, 1<1</г. Определим (2 X 2)-матрицу (или Rt], если ясно, ка-

ковы flo и Oi) для 0<t</</j условиями

для 1>0,

1) Ri,=

ГО 1 1

ГО 1

0 1

»...»

.1 -

2) если / > t, то Ri]=

Пример 8.10. Пусть ао=57 и ai=33, последовательность остатков есть 57, 33, 24, 9, 6, 3, а частные qi, l<i<4, равны 1, 1, 2, 1. Тогда □ □

Р(67.33) 04 -

0 г

"0 г

"0 Г

"0 г

.1 -Ij

1 -2

.1 -1.

.1 -1.

Два интересных свойства этих матриц описаны в следующей лемме.

Лемма 8.5.

(б) Ro,=

для К К к,

для О < / < ft.

Xj+i

еде числа at, Xt, yt определяются расширенным алгоритмом Евклида.

Доказательство. Элементарное упражнение на применение индукции. □



8.9. АЛГОРИТМ НАХОЖДЕНИЯ НОД ПОЛИНОМОВ

Заметим, что все построения этого раздела годятся и для полиномов от одной переменной. Надо лишь учесть, что, в то время как наибольший общий делитель двух целых чисел определяется однозначно, для полиномов с коэффициентами из некоторого поля наибольший общий делитель единствен только с точностью до умножения на элемент поля. Иными словами, если g{x) делит полиномы ав(х) и ai(x) и всякий другой их делитель тоже делитg(л:), то полином eg-(л:), где с - отличная от нуля постоянная, также обладает этим свойством. Нас удовлетворит любой полином, который делит ао{х) и ai{x) и делится на любой их делитель. Чтобы обеспечить единственность, мы могли бы (но не будем) требовать, чтобы наибольший общий делитель был нормированным, т. е. чтобы коэффициент при его старшем члене был равен 1.

8.9. АСИМПТОТИЧЕСКИ БЫСТРЫЙ АЛГОРИТМ НАХОЖДЕНИЯ НОД ПОЛИНОМОВ

При построении алгоритмов для нахождения наибольшего общего делителя мы меняем нашу схему и рассматриваем сначала случай полиномов, поскольку в случае целых чисел приходится преодолевать дополнительные трудности. Пусть Со (х) и d (х) - два полинома, наибольший общий делитель которых надо вычислить. Мы предполагаем, что CT(ai (л:))<СТ(а» (л:)). Легко добиться выполнения этого условия, а именно: если CT(ao)=CT(ai), то заменяем полиномы По и Ci полиномами ai и ао mod Ci, т. е. вторым и третьим членами последовательности остатков, и работаем, отправляясь от них.

Разобьем нашу задачу на две части. Первая состоит в построении алгоритма, отыскивающего последний член последовательности остатков, степень которого больше половины степени полинома Оо. Формально, пусть I (i) - то единственное целое число, для которого CT(a/(,))>f и CT(a;(f)+i)i. Заметим, что если ао имеет степень п, To/(i)n-i-1 в предположении, что CT(ai)<CT(ao). поскольку CT(ai)CT(ai-i)-1 для всех

Введем рекурсивную процедуру ПНОД (полуНОД), которая по полиномам Со и Сь таким, что CT(ao)>CT(ai), формирует матрицу Roj (см. разд. 8.8), где j=l(n/2), т. е. aj- последний член последовательности остатков, степень которого больше половины степени полинома ао.

В основе ПНОД-алгоритма лежит тот факт, что частные от деления полиномов степеней di и dj, di>d2, зависят только от 2 (d,- -d2)+l старших членов делимого и di-d2+l старших членов делителя. Процедура ПНОД приведена на рис. 8.7.

Пример 8.11. Пусть

piix) = x. + x*+x + x + x + l



(х) = х* - 2х + Зх-х-7.

Допустим, мы пытаемся вычислить ПН0Д(р1, ра). Если ao=Pi и ai=P2, то в строках 2 и 3 т=2 и

Ь, = х + х + х+1, с, = х+1, bi = x-2x + 3, с, = -л:-7.

Затем вызываем ПНОД(Ьо, bi) в строке 4. Можно проверить, что на этом шаге

ГО 1 1

.1 -( + 3). •

1 О О 1

procedure ПНОД(ао, а,):

1. if СТ(а,Х СТ(ао)/2 tlien return

else begin

2. пусть Co = V" + o. где m= LCT(a„)/2 J и CT(c„)< m;

3. пусть abiX + Ci, где CT(Ci)< m;

7. 8.

9. 10.

comment bg и 6, - старшие члены полиномов и а,.

Имеем СТ(Ьо) = Г СТ(ао)/21 = CT(a.)-CT(ai); /?ПН0Д(6„,

" d

. «1.

и CT(6„)-CT(bJ =

/•<-d mode;

comment e и -соседние члены последовательности остатков, их степень не превосходит f 3m/2 ", т. е. »/4 степени полинома Ср; пусть e = g,xf-"J + h„, где CT(/i„)< L SJ; пусть f = gxn/iJ + hi, где CT(/ii)< Ln/ZJ: comment степени полиномов g и g-j не превосходят

т + 1; S -ПHOД(g„, gi); id/ej;

О Г

return S end

[1 -q

Рис. 8.7. Процедура ПНОД.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 [109] 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022