2.2.2. Алгоритм Евклида и теорема Ламе

Теперь мы изложим классический алгоритм Евклида вычисления наибольшего общего делителя двух целых чисел. Свойство евклидовости утверждает, что для целого числа а и ненулевого целого числа b существует единственные частное q и остаток , такие, что . В упр. 1 по программированию для разд. 2.2.1 требуется написать подпрограммы , которые возвращают частное и неотрицательный остаток от деления а на b; эти подпрограммы будут использоваться в различных утверждениях и в описаниях других алгоритмов на протяжении всей этой книги.

Ключевым в алгоритме Евклида является следующий факт: если и d делит а и b, то (упр. 3 разд. 2.2.1). Поскольку это верно для любого делителя, это верно и для значит, Кроме того, для всякого a; условимся также считать равным нулю. Итак, если заданы целое число а и ненулевое целое число 6, мы выполняем такую последовательность делений:

Пусть тогда

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

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

ЕА. Алгоритм Евклида (Euclidean Algorithm)

Вход:

Выход:

1. [Инициализация]

2. [Основной цикл] Пока выполнять

3. [Выход] Вернуть

Рассмотрим пример Алгоритм Евклида вычисляет последовательность таким образом,

Анализ времени работы алгоритма ЕА. Предположим без потери общности, что а 6.

Поскольку шаги 1 и 3 выполняются за время очевидно, что время работы алгоритма Евклида определяется временем выполнения шага 2.

На шаге 2 выполняется целочисленных делений, и нам необходимо оценить сверху ; однако, прежде чем сделать это, заметим, что первое деление выполняется с числами a и b, а из разд. 1.2 мы знаем, что Так как последующие деления выполняются с меньшими числами, то выражение ограничивает сверху время выполнения для всех остальных делений. Поэтому можно утверждать, что в наихудшем случае каждое деление выполняется за время

Далее, для того чтобы вычислить верхнюю границу для числа (целочисленных делений, необходимых для нахождения наибольшего общего делителя а и b), используем теорему Ламе, сформулированную ниже; по этой теореме число 5 -(количество цифр в меньшем числе) является верхней оценкой числа , и в нашем случае получаем

Таким образом, (число делений) (время выполнения каждого деления) откуда получаем

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

Теорема Ламе (Ьатё, 1844) (оценка наихудшего случал для алгоритма Евклида). Количество делений, которое нужно выполнить для нахождения наибольшего общего делителя двух целых чисел, не превосходит количества цифр в меньшем числе, умноженного на пять.

Доказательство. Рассмотрим последовательность Фибоначчи (см. историческое замечание 2)

в которой каждый член равен сумме двух предыдущих. (Заметим, что 1 — единственное число, которое появляется дважды; для оставшейся части доказательства последовательность {1,1,2,3,5,8} эквивалентна {1,2,3,5,8}.)

Нетрудно показать, что число членов в последовательности Фибоначчи, имеющих одинаковое количество цифр, не меньше четырех и не больше пяти. Действительно, если мы обозначим через первый член с цифрами, то очевидным образом выполняются неравенства

так как есть сумма двух членов с к цифрами. Точно также, поскольку

и имеем

Аналогичным образом получаем следующие неравенства:

Поэтому группа членов, содержащих цифр, имеет не меньше четырех и не больше пяти элементов.

Если обозначить через члены последовательности Фибоначчи, то число членов, предшествующих не больше,

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

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

Теперь рассмотрим случай т.е. при каком-то делении в алгоритме Евклида мы получим (наименьшее Пусть — два последовательных числа Фибоначчи, между которыми содержится тогда

и

откуда следует, что . Если также меньше, чем , то интервал будет пустым. С другой стороны, если , то, так как должно вьтолняться неравенство , т.е. интервал будет пустым. Таким образом, если частное в алгоритме Евклида отлично от единицы, то найдется хотя бы один интервал в последовательности Фибоначчи, который не будет содержать остатков, и это не восполнится интервалом с двумя остатками.

Итак, для того чтобы последовательность остатков имела ту же длину, что и последовательность частные во всех операциях деления должны быть равными единице, так же как и . Как и в случае последовательности Фибоначчи, где в последовательности остатков должно быть однако не может равняться двум, поскольку тогда эти две последовательности были бы одинаковыми и 6 было бы равно что не так. Следовательно, должно быть равно как минимум трем и последовательность остатков будет иметь строго меньшую длину, чем последовательность Фибоначчи.

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

Лемма 2.2.9. Если , то .

Доказательство. По определению и, очевидно, Поэтому и для доказательства леммы нужно рассмотреть два случая:

Теорема 2.2.10 (другая оценка наихудшего случая для алгоритма Евклида). Пусть a и b — целые положительные числа и . Количество делений, которое нужно выполнить для нахождения наибольшего общего делителя a и b, не превосходит

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

Пример. Оценим число делений, необходимое для вычисления (144,89) и (21,13). По теореме Ламе в обоих случаях число делений меньше, чем используя теорему 2.2.10, получаем, что число делений в первом случае не больше 15, во втором — не

больше 9; на самом деле (144,89) вычисляется после 9 делений, а (21, 13) - после 5.

Приведем в заключение интересный результат Дирихле (Dirich-let, 1849), утверждающий, что если а и b — два случайно выбранных целых числа, то вероятность того, что равна . (Другие результаты по этой тематике можно найти в работах (Абрамов, Рыбин, 1988; Bradley, 1970; Collins, 1974; Knuth, 1969; Lipson, 1981; Motzkin, 1949 и Schroeder, 1986).)