Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 103
Текст из файла (страница 103)
А число С также делит все число С, так что оно делит н остаток Г; таким образом, большее число делит меньшее, а это невозможно. Таким образом, нет такого числа, большего, чем Р, которое бы делило А и С; значит, число Г является наибольшим общим делителем. Следствие. Это рассуждение делает очевидным предложение, что всякое число, делящее два числа„делит и их наибольший общий делитель.
Ч. Т. Д. Формулировка Евклида упрощена здесь в одном немаловажном аспекте, Греческие математики не считали единицу "делителем" другого положительного числа. Два положительных целых числа были либо оба равны единице, либо взаимно просты, либо имели наибольший общий делитель. Фактически единица даже не считалась числом, а нуль, конечно, вообще не существовал. Эти довольно нескладные соглашения были причиной того, что Евклид должен был дублировать значительную часть своих рассуждений, и он дал два отдельных предложения, каждое из которых по существу сходно с вышеприведенным. В своем доказательстве Евклид впервые предлагает повторно вычитать для каждой пары текущих значений меньшее число из большего до тех пор, пока в результате получатся два числа, одно из которых кратно другому.
Но при доказательстве он фактически берет остаток от деления одного числа иа другое, а так как понятие нуля отсутствовало, ои не может говорить об остатке, когда одно число делит другое. Поэтому резонна заявить, что он рассматривает каждое деление (а не каждое вычитание в отдельности) как один шаг алгоритма, и, следовательно, "аутентичное' изложение его алгоритма выглядит следующим. Алгоритм Е (Оригияальямй алгоритм Евклида). По двум целым числам А и С, ббльшим единицы. этот алгоритм находит их наибольший общий делитель.
Е1. (А делится иа С'?) Если С делит А, то алгоритм заканчивается, давая в качестве результата число С. Е2. (Заменить Л остатком,) Если А шо4 С равно единице, то заданные числа взаимно просты, поэтому алгоритм заканчивается. В противном случае заменить пару значений (А, С) парой (С, А шоб С) и вернуться к шагу Е1.
1 "Доказательство" Евклида, приведенное выше, представляет особый интерес, так как оио в действительности совсем не является доказательством! Евклид проверяет результат алгоритма только тогда, когда шаг Е1 выполняется либо один раз, либо три раза. Он, безусловно, должен был понимать, что шаг Е1 может выполняться болыпе трех раз, хотя и не упоминает о такой возможности. Не имея представления о доказательстве при помошп математической индукции, он мог привести доказательство только для конечного числа случаев. (Фактически, желая доказать теорему для общего случая я, он рассматривал только частиый случай и = 3.) Хотя алгоритм Евклида заслуженно известен своим большим вкладом в искусство логической дедукции, приемы, применяемые в строгих доказательствах по индукции, были открыты только спустя многие столетия, а ключевые идеи, используемые для доказательства справедливости алгоритмов, становятся по-пастоящему понятными только сейчас.
(Полное доказательство алгоритма Евклцла, а также краткое обсуждение основной процедуры доказательства алгоритмов изложены в разделе 1.2.1.) Следует отметить, что этот алгоритм нахождения наибольшего общего делителя был выбран Евклидом в качестве первого шага в его изложении теории чисел. И в наши дии во многих учебниках все еще используется тот же порядок изложения.
Евклид дал, кроме того, метод (предложение 34) нахождения паимеиыпего общего кратного двух целых чисел и и э, а именно: разделить и на ясб(и,э) и затем умножить результат па е; это равносильно соотношению (10). Если пренебречь предубеждением Евклида против чисел О и 1, то алгоритм Е можно переформулировать следующим образом.
Алгоритм А (Алгориш и Евклида и современной редакции). По данным иеотрица тельным целым числам и и е этот алгоритм находит их наибольший общий делитель. (Замечаяие. Наибольший общий делитель пропзвольимх целых чисел и и е можно получить с учетом соотношений (2) и (3), применив алгоритм к (и~ и (эЦ А1, (и = О?) Если и = О, то выполнение алгоритма закаичиваегся, а в качестве результата возвращается число и. А2. (Взять и шоб о.) Присвоить т <- и шоб и, и <- э, и <- г и вернуться к шагу А1. (В результате выполняемых па этом шаге операций значение е уменьшается, значение йсо(и,и) остается неизменным.) Например, можно вычислить Нсд(40902, 24140) следующим образом: Нсб(40902, 24140) = Нсб(24140, 16762) = Нсд(16762, 7378) = Нсс((7378, 2006) = Нсб(2006, 1360) = Нсд(1360, 646) = Нсб(646,68) = Нсд(68,34) = Но((34,0) = 34.
Справедливость алгоритма А легко доказать из соотношения (4) и уравнения Нсд(и,е) = Нсб(е, и — 7е) (13) для любого целого числа 7. Уравнение (13) выполняется потому, что любой общий делитель чисел и и е является делителем как е, так и и — 7е, и наоборот, любой общий делитель чисел е и и — де должен делить оба числа и и е. В слелующей Н1Х-программе показано, что алгоритм А может быть легко реализовал на компьютере. Программа А (Алгорипьи Евклида). Положим, что и и е — неотрицательные целые числа однократной точности, помещенные в ячейки 0 и 7 соответственно; зта программа помещает Но<1(и, е) в ячейку гА.
1,0Х 0 ЛНР 2Р 1Н ЯТХ 7 ЯНАХ $ 017 7 2Н ЬВА 7 ВАХИН 18 1 гХ+- и. 1 Т е+-ЕХ. Т гАХ с- гА. Т гХ <- гАХюобе. 1+Т гА<-е. 1+ Т Выполнено, если гХ = О. 1 Время выполнения программы составляет 19Т + 6 циклов, где Т вЂ” число выполненных операций деления. Рассуждения, приведенные в разделе 4.5.3, показывают, что в случае, когда и и е независимо и равномерно распределены в интервале 1 < и,е < )7, среднее значение Т можно приблизительно представить в виде Т = 0.8427661п)7 + 0.06. Бинарный метод. После стольких столетий применения почтенного алгоритма Евклида несколько неожиданным оказалось то, что он не всегда является лучшим способом определения наибольшего общего делителя. В 1961 году Джозеф Стейн (ЛоееГ Бге1п) предложил совершенно другой алгоритм нахождения наибольшего общего делителя, ориентированный, прежде всего, на двоичную арифметику [см.
1. Сотр. Рйуя, 1 (1967), 397-405]. Этому новому алгоритму совершенно не нужны команды, выполняющие операции деления. Основанный исключительно на операциях вычитания, он проверяет, четно ли число, и делит пополам четнью числа (что соответствует в двоичной арифметике сдвигу вправо). Бинарный алгоритм нахождения наибольшего общего делителя основан на четырех простых фактах относительно положительных целых чисел и н е.
а) Если и и е оба четны, то Но1(и, е) = 2 Нсд(и/2, е/2) [см. уравнение (8)]. Ь) Если и четно, а е нечетно, то Нсб(и, е) = Нсб(и/2, е) [см. уравнение (6)], с) Как и в алгоритме Евклида, Нсб(и, е) = Нсд(и — е, е) [см. уравнения (13) и (2)]. 6) Если и и е оба нечетны, тон-е четно и ]и — е] < пшх(и,е), Алгоритм В (Бинарный алгориньн нахооюденил наибольтиеео ойцего делителя). По даннгям целым числам и и е этот алгоритм (рис, 9) находит наиболыпнй общий делитель, В1.[Найти степень 2.] Присвоить й +- О, затем повторно присваивать й +- л + 1, и +- и/2, е +- е/2 нуль или более раз до тех пор, пока оба числа и и е станут нечетными.
В2. (Начальная установка.] (Исходные значения чисел и и е уже разделены на 2", и по крайней мере одно из текущих значений нечетно.) Если нечетно и, то присвоить г +- -е и перейти к шагу В4. В противном случае присвоить г +- и. ВЗ. (Уменьшить с наполовину.) (Здесь с четно и не нуль.) Присвоить г ~/2. В4. (т четно7] Если с четно, то вернуться к шагу ВЗ.
Вб. (Установить шах(и,е) заново.] Если 1 > О, то присвоить и +- 1, в противном случае присвоить е <- -г. (Большее из чисел и и е заменяется на ]Ц за исключением, возможно, первого выполнения этого шага,) Вб. (Вычесть.] Присвоить | ~- и — е. Если г ф О, то вернуться к шагу ВЗ. В противном случае алгоритм останавливает выполнение, а на выходе будет и 2~. ! В качестве примера работы алгоритма В рассмотрим случай с числами и = 40902, е = 24140, т.
е, с теми же числами, которые использовались при проверке работы алгоритма Евклида На шаге В1 выполняются присвоения й +- 1, и < — 20451, е <- 12070. Затем 1 присваивается значение -12070, которое заменяется значением †60; после этого значение е заменяется числом 6035 и вычисления продолжаются следующим образом.
Результат равен 17 2~ = 34. Здесь нам пришлось выполнить немного больше итераций, чем при работе с алгоритмоч А, но каждая из них выполнялась проще, так как совершенно отсутствовали операции деления. Для разработки ИХХ-программы, реализующей алгоритм В, потребовалось немного больше команд, чем для реализации алгоритма А. Чтобы получить программу, типичную лля двоичного компьютерного представления алгоритма В, предположим, что компьютер И1Х расширен путем включения следующих операторов. ° 81 В (сдвинуть влево как двоичный код в АХ).
С = б: Р = 6. Содержимое регистров А и Х "сдвигается влево" на М двоичных разрядов, т, е. ]гАХ] +- ]2ыгАХ] шод В~о, где Б — размер байта. (Как и во всех других командах сдвига в И1Х, знаки регистров гА и гХ не изменяются.) 20451 6035 901 6035 901 2567 901 833 17 833 17 51 17 17 +14416, +7208, +3604, +1802, +901 -5134, -2567 -1666, -833 +68, +34, +17 -816, -408, -204, -102, -51 -34, -17 0 Рне.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
