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

procedure НОД(ао. i): 1. if а, делит а„ tlien return а, else begin ?*-ПНОД(а„, fli);

2. 3, 4.

5. 6.

if b, делит fe„ then return b, else begin с •<-b„ modbi, return HOJlibi, c) end

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

Поэтому в строке 3 вычисляем

Ьо = 4л; -7х+ 11л; + 22,

16- 16- 8 •

Обнаруживаем, что bt не делит Ьо В строке 5 находим, что 6„ modfe, =3952x + 3952.

Так как последний полином делит bi, то вызов процедуры НОД в строке 6 завершает работу в строке 1 и выдает в качестве ответа 3952х+3952. Разумеется, х+1 также является наибольшим общим делителем для /?, и р,. О

Доказательство корректности алгоритма 8.7 тривиально, если доказать, что он заканчивает свою работу. Таким образом, корректность алгоритма вытекает из анализа времени его работы, что составляет содержание следующей теоремы.

Теорема 8.19. Если CT{pi)=n, то алгоритм 8.7 выполняется за Оа(М(п) log п) ишгов, где М(п) - время умножения двух полиномов степени п.

Доказательство. Неравенство

Г(п)<Г (±+c,M(n)+CiM (л) logn.

(8.28)

где с, и Сг - постоянные, описывает время работы алгоритма 8.7. Действительно, степень полинома bi меньше половины степени



полинома Оо, так что первое слагаемое в (8.28) отражает рекурсивный вызов в строке 6. Слагаемое CiM{n) отражает деления н умножения в строках 1, 3-5, cMin) log п - вызов процедуры ПНОД в строке 2. Легко видеть, что решение неравенства (8.28) ограничено сверху функцией кМ{п) log п, где k - некоторая постоянная. □

Следствие. НОД двух полиномов степени не выше п можно вычислить за время Оа(п logn).

8.10. НОД ЦЕЛЫХ ЧИСЕЛ

Обсудим кратко изменения, которые надо произвести в процедурах ПНОД и НОД, чтобы они годились для целых чисел. Чтобы понять, где возникают трудности, вернемся к лемме 8.6, показывающей, что при нахождении частных от деления полиномов степеней п и п - d нам ни в одном из них не нужны члены степени, меньшей п-2d.

По аналогии с леммой 8.6 можно рассмотреть два целых числа / и g, f>g, и записать их в виде /=/i2*+/2 и g=gi2*+gt2, где /2<2* и 2<2*. Вместо условия CT(gi{x))lfiT(fi{x)) можно предполагать, что /i<(gi) Тогда можно считать, что f=qg+r и fi=qigi+ri. Комбинируя эти формулы, получаем

gi2* (<7 9,) = /, + r,2*-9g,-r. (8.29)

Так как ri<gi, /2<2* и все эти целые числа неотрицательны, легко вывести из (8.29), что q-iO. Пусть q=qi-т для некоторого тО. Тогда из (8.29) заключаем, что

"gi2* qg2 + r = [q, -т) g + г.

Следовательно,

mg = mg,2* Н- mg, < q,g, -f л. (8.30)

Поскольку/l<(gl) Toig,. Крометого, по условию g2<2* и/<g, так что из (8.30) вытекает, что

ng<g,2> + g2g. (8.31)

Теперь из (8.31) непосредственно следует, что /л<2. Отсюда заключаем, что или q=qi, или q=qi-1.

В первом случае нет трудностей. Если же q=qi-1, то нельзя рассчитывать, что процедура ПНОД сработает правильно. К счастью, можно показать, что i, только если 9-последнее частное в последовательности остатков, для которого процедура ПНОД строит матрицу. Иными словами, подставляя-9i = - 1 в (8.29), получаем

r = /, + r,2*-9g2 + g:2*. (8.32)



Так как r<g=gi2+gi, то из (8.32) вытекает /i2*+/a<g2(l+(7) и тем более ri<l--, а значит, rj<.qi.

Итак, число ги которое стоит в последовательности остатков после /, и gi, должно быть меньше fi/gi. Поскольку giVfu то /-,< <K/i. а это означает, что процедура ПНОД выдала бы матрицу, содержащую частные вплоть до fi/gi, но не далее. Если эта матрица используется в строке 5 процедуры ПНОД, то может оказаться, что число /, вычисляемое в строке 6, будет не меньше al. Но поскольку ошибка в последнем частном равна всего 1, можно показать, что продолжение последовательности остатков на ограниченное число членов (не зависящее от размера Оо) после выполнения строки 6 будет достаточно для того, чтобы один из очередных членов этой последовательности стал меньше аУ*. Аналогичный прием надо применить и после строки 5 процедуры НОД.

Еще один круг трудностей связан с леммой 8.6. В случае полиномов мы смогли показать, что в последовательности остатков, образованной с привлечением старших членов полиномов, определенные члены высокого порядка совпадают с соответствующими членами в последовательности, образованной по всем членам полиномов. Аналогичный результат приближенно выполняется и для целых чисел при условии q=qi. Однако можно только ограничить разность между г и ri2* числом 2*(9+1); нельзя гарантировать, что какие-нибудь конкретные разряды чисел г и ri2* будут совпадать. Тем не менее такой источник "ошибок округления" приведет к тому, что после выполнения строки 6 процедуры ПНОД и строки 5 процедуры НОД в последовательности остатков понадобится лишь ограниченное число дополнительных членов.

Из-за продолжения последовательности остатков на ограниченное число членов, сложность алгоритма увеличивается на Об{М (п)), где М (п) - время умножения п-разрядных двоичных чисел, так что анализ времени работы процедур ПНОД и НОД, по существу, не изменится. Поэтому справедлива следующая теорема.

Теорема 8.20. Если М (п) - время умножения двух п-разрядных двоичных целых чисел, то существует алгоритм, отжкиваюш,ий их наибольший обилий делитель за Об(Л1 (п) log п) шагов.

Доказательство. Упражнение на предложенную выше модификацию процедур ПНОД и НОД. □

Следствие. НОД двух целых чисел можно найти за время Ов{п log" п log log п). О





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.0021