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

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

По аналогии с леммой 8.6 можно рассмотреть два целых числа и записать их в виде где Вместо условия можно предполагать, что Тогда можно считать, что Комбинируя эти формулы, получаем

Так как и все эти целые числа неотрицательны, легко вывести из (8.29), что Пусть для некоторого Тогда из (8.29) заключаем, что

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

Поскольку то Кроме того, по условию так что из (8.30) вытекает, что

Теперь из (8.31) непосредственно следует, что Отсюда заключаем, что или или .

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

Так как то из (8.32) вытекает и тем более а значит,

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

Еще один круг трудностей связан с леммой 8.6. В случае полиномов мы смогли показать, что в последовательности остатков, образованной с привлечением старших членов полиномов, определенные члены высокого порядка совпадают с соответствующими членами в последовательности, образованной по всем членам полиномов. Аналогичный результат приближенно выполняется и для целых чисел при условии Однако можно только ограничить разность между числом нельзя гарантировать, что какие-нибудь конкретные разряды чисел будут совпадать. Тем не менее такой источник "ошибок округления" приведет к тому, что после выполнения строки 6 процедуры ПНОД и строки 5 процедуры НОД в последовательности остатков понадобится лишь ограниченное число дополнительных членов.

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

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

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

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