Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 104
Текст из файла (страница 104)
9. Бинарный алгорнтм нахождения наибольшего общего делителя. ° ЯВВ (сдвннуть вправо двончный кода АХ). С = 6, "Р = 7. Содержимое регистров А и Х "сдвигается вправо" на М двоичных разрядов, т. е, )гАХ! е- '()гАХ))2м). ° ЛАЕ, ЛАО (переход, если в регистре А находятся четное число; переход, если в регистре А находится нечетное чнсло).
С = 40; Р = 6, 7 соответственно. Переход выполняется, если в регистре гА находится четное нлн нечетное число соответственно. ° ЗХЕ, ЗХО (переход, если в регистре Х находятся четное число; переход, если в регистре Х находится нечетное чнсло). С = 47; Г = б, 7 соответственно. Этн олерацвн аналогичны ЛАЕ, ЗАО. Программа В (Вииаримй «лгорипьи нахождения наибольшего общего делит«ела). Пусть и н е — положнтельные целые чнсла с однократной точностью, помещенные соответственно в ячейки памяти О и Ч. Эта программа, нспользуя алгоритм В, помещает Ясд(и, е) в гА. Содержнмое регистров таково: гА ьв 1, гП гн А.
В1. Найти степень 2. гХ+- и. гА+- -е. 01 АВЯ ЕОО ОЗ В1 ЕИТ1 ОЮ 1.ОХ 04 1ОАИ ОЗ ЛИР 00 2Н ЯВВ 07 1ИС1 08 ЯТХ ОУ ЯТА 10 1Н ЗХО 11 В2 ЛАЕ 10 ЫА 11 ВЗ ЯЗВ Ц В4 ЛАЕ 1:Ь О О 1Р 1 1 У т(АВЯ) В4 2В О 1 ВЗ 1 1 1 1 А А А А 1+А В+А В В 1 — В+В Разделить пополам гА, гХ.
А <- А+ 1. е +- и1'2. е е- е/2. Перейти к шагу В4 е 1+- -е, если е нечетно. ВЗ. Начальная сшиеака. 1+- и. ВЗ, Раг лиг пополам 1. геь ийу 15 Вб 16 17 18 12 1Н 22 ВВ 21 гн 22 22 2( зАН 1Г ЗТА О ВОВ Ч ЗНР гр втА ч(Авв) АОО ЗАНХ ВЗ 1ЛА О внтх о 51В О,1 с Е Е Е С вЂ” Е С вЂ” Е с 1 1 1 В . 'становвть заново щах(и„х), Если 1 > О, присвоить и +- А 1+- в — а Если 1 < О, присвоить з <- -1. Вб. .Вычесюь. Перейти х шагу ВЗ, если 1 Ф О. гА+- в. гХ <- О. тА+-2 гА. А Время выполнения программы равно 9Л+ 2В+ ОС+ ЗХ>+ Е+ 13 машинных циклов. Здесь Л = А, Е = 1, если на шаге В2 произошло присвоение 1 +- и (иначе В = О), С вЂ” число шагов, на которых выполняется вычитание, )0— число делений пополам на шаге ВЗ и Š— число, показывающее, сколько раз имеет место неравенство на шаге В5.
Из вычислений, выполняемых ниже в этом разделе, следует, что в качестве средних значений этих величин в предположении, что входные величины и и в являются случайными в диапазоне 1 < и, и < 2 ., можно взять Л = -', В = -', С = 0.71)Ч вЂ” 0.5, 11 = 1.41Ю вЂ” 2.7 и Е = 0.351Ч вЂ” 0.4. Поэтому общее время выполнения программы составляет примерно 8.8% + 5.2 циклов; для программы А при тех же предположениях оно равно приблизительно 11.1Ю+ 7.1 циклов. Наихудшее возможное время выполнения 13)Ч + 8 циклов будет при Л = О, В = 1, С = )Ч, 11 = 2Ж вЂ” 2, Е = 1Ч вЂ” 1, т.
е. при условии, что и и с принадлежат одному и тому же диапазону. (Соответствующее время выполнения программы А равно 28.8)Ч + 19 циклов.) Таким образом, более высокая скорость выполнения итераций в программе В за счет простоты операций компенсирует большее число итераций, требуемых для выполнения программы. Мы уствновили, что бинарный алгоритм на компьютере МХХ выполняется на 20% быстрее, чем алгоритм Евклида. Безусловно, при реализации алгоритма на других компьютерах ситуация может измениться, но во всяком случае оба алгоритма достаточно эффективны. Тем не менее оказывается, что даже такая освященная векамн процедура, как алгоритм Евклида, не может противостоять прогрессу.
История бинарного алгоритма нахождения наиболыпего общего делителя поразительна: он был известен еще в Древнем Китае. Так, в разделе б главы 1 классического труда СЬш СЬапн анап Ейп (" Девять разделов арифметики", ок. 1 в. н. э.) приведен следующий метод приведения дроби к простейшему виду. Если возможно выполнение паловпнного деления, выпалннть его.
В противном случае выписать знаменатель и числитель дроби н вычесть меньшее число вз большего. Повторять эту операпию ло тех пор, пока числа не станут равными. Сократить дробь нз зто общее значение, Если повторная операция снова приводит к половинному делению вместо того, чтобы повторять операцию вычитания (этот пункт не совсем понятен), метод фактически совпадает с алгоритмом В. [См. У. Чйапп', ТЬе Веге)оршепс оГ Ма1Ьеи агксэ ш СЛта алг(,7арап (1.е(рв18, 1913), 11; К. Уойе!, №ип ВбсЬег аНгЛтегисЛег ХесЛпй (ВгаипвсЬте(8: У1еие8, 1968), 8.) В, К. Харрис (Ъ'. С. НагНв) (НЬопассю' Оилггег)у 8 (1970), 102-.103; см.
также г'. А. ЬеЬевйие, Х МагЛ. Рнгев Аррй 12 (1847), 497-520) предложил интересный гибрид метода Евклида и бннарного метода. Если числа и и и нечетны и и > и > О, то всегда можно написать где 0 < г < и и г четно. Если т зв О, то присваиваем г <- г/2 до тех пор, пока значение г не станет нечетным.
После этого присваиваем и +- с, с +- г и повторяем процесс. В последующих итерациях д > 3. 8п)(им ию..., и„) = бед(иц бег((из,..., и )) . (14) Чтобы вычислить бсср(ии ив,..., и„), можно поступить так. Алгоритм С (Наибольший общий давитлель а целых чисав). По заданным целым числам им ию ..., и„, где и > 1, этот алгоритм вычисляет их наибольший общий делитель, используя алгоритм для случая и = 2 квк подпрограмму.
С1. Присвоить Ы +- и„, (г +- п — 1. С2. Если д ~ 1 и й > О, то пРисвоить И <- бсср(вы г() и й е- й — 1 и повтоРить этот шаг. В противном случае б = 8сг)(им..., ин) ! Данный метод сводит вычисление бед(им..., ии) к повтоРным вычислениЯм наибольшего общего делителя двух чисел. В нем используется то обстоятельство, что бсг((им..., иы 1) = 1. Оно оказывается полезным, поскольку, как отмечалось выше, в 61 случае нз 100, если числа и„1 и и рассматривать в качестве случайных, выполняется равенство йсб(и„ми„) = 1. В большинстве случаев значение б на нескольких первых этапах вычисления быстро уменьшается, в результате чего оставшаяся часть вычислений выполняется очень быстро. Здесь алгоритм Евклида имеет преимущество над алгоритмом В ввиду того, что время его выполнения определяется, прежде всего, значением гпш(и,с), в то время как время выполнения алгоритма В зависит, главным образом, от значения гпах(и, и).
Поэтому целесообразно выполнять одну итерацию алгоритма Евклида, заменяя число и на и щи и, если и значительно больше числа и, а затем продолжать вычисления по алгоритму В, Обобщения. Методы, используемгяе для вычисления бсср(и,и), можно обобщить так, чтобы решать немного более сложные задачи. Например, предположим, нужно вычислить наибольший общий делитель и целых чисел им ив, ..., и„. Один из способов вычисления бсб(имию...,и„), если предположить, что все числа из неотрипательны, состоит в обобщении алгоритма Евклида следующим образом: если все числа и1 равны нулю, то наибольший общий делитель принимается равным нулю, иначе при наличии только одного ненулевого числа иу это число н будет наибольшим общим делителем; в противном случае заменяем ив на ив пкх1 и.
для всех к ф у, где и. †минимальн из ненулевых чисел и, и повторяем процесс. Алгоритм, набросок которого здесь приведен, является естественным обобщением алгоритма Евклида. Он может быть обоснован аналогичным образом. Но име.
ется более простой метод, основанный на легко проверяемом тождестве Утверждение, что значение бсб(и„ми„) будет равно единице в более чем 60 случаях из 100 для случайных исходных данных, является следствием хорошо известного результата теории чисел. Теорема 12 (Г.
Люсьен Дирихле (О. Ее)еппе П(г(сЫес), АЬЬапс()индел Кап1д))с)с Ртепб. Айи(. 110гг. (1649), 69-83). Если и и е — случайно выбираемые целые числа, то вероятность того, что кос)(и, е) = 1, равна б/хз ы .60793. Точная формулировка этой теоремы, в которой четко определяется, чтб имеется в виду под словами "выбирается случайно", а также ее доказательство приводятся в упр.
10. Здесь же ограничимся эвристическим доказательством, показывающим, почему эта теорема правдоподобна. Если принять без доказательства существование вполне определенной вероятности р тога, что и .1. е, то можно определить вероятность того, что выполняется равенство бсц(и,е) = И для любого положительного целого числа Ы, так как бсц(и, е) = д тогда и только тогда, когда число и кратно с(, число е кратно сс и и/И .С. е/И. Поэтому вероятность того, что бес)(и, е) = с(, равна 1/И, умноженному на 1/с(, умноженному на р, т. е. р/~(з. Просуммируем теперь эти вероятности по всем возможным значениям с(. Должно получиться Р/с( = Р(1+ з + 2 + сг + ' ' ' ) ' Так как сумма 1+ 4+ г + ° ° ° = Н~ равна;гз/6 согласно формуле 1.2.7-(7), для того, чтобы выполнялось предыдущее соотношение, необходимо, чтобы р = 6/зз.
! Алгоритм Евклида можно обобщить еще одним способом, имевшим большое значение. Можно вычислить целые числа и' и е', такие, что ии'+ее' =бесс(и,е). Одновременно вычисляется и ксс)(и, е). Это обобщение алгоритма Евклида удобно описать, используя векторные обозначения. Алгоритм Х (Обобщенный алгоритм Евклида). Для заданных неотрицательных целых чисел и и е этот алгоритм определяет вектор (и1„из, из), такой, что ии1 + сиз = из = бес)(и, е). В процессе вычисления используются вспомогательные векторы (ем из,ез), (Сс, Сз, Сэ); действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения исз+ ест = сз, ии1+еиз = из, ив~+сиз = из (16) Х1.
~Начальная установка.] Присвоить (им из,из) +- (1,0,и), (еыез,ез) +- (0,1,е), Х2. ]ез = О?] Если ез = О, то выполнение алгоритма заканчивается. Х3. ]Разделить и вычесть.] Присвоить 9 <- (из/ез], затем присвоить (Сс,гз,гз) +-(имиз,из) — (еыез ез)9 (ис, из„из) 4- (еы ез, ез) (еы ез, ез) +- (Сы сз, гз) Возвратиться к шагу Х2. 2 Например, пусть и = 40902, е = 24140. На шаге Х2 получаем сведующее. е2 ез 1 24140 -1 16762 2 7378 -5 2006 17 1360 -22 646 61 68 -571 34 1203 О д и~ из — 1 0 1 О 1 1 1 -1 2 — 1 2 3 3 -5 1 -10 17 2 13 -22 9 -Зб 61 2 337 -571 пз с~ 40902 О 24140 16762 -1 7378 3 2006 -10 1360 13 646 -36 68 337 34 -710 (17) (18) Введем вовую переменную (10/3) и + (3/3) к + ~3/3) р + (8/3) з = Зш + я + у + 2з = 1) и используем ее для исключения у.
Уравнение (17) примет вид (10 аз) +(3 бз)я+31,+(8 бз) =ю+зг,+2 =1, (19) а уравнение (18) останется неизменным. Используем новое уравнение (19) для исключения и, тогда (18) примет вид 6(1- 31~ — 2г) — 7я — бг = 2 Позтому решение имеет вид 337 40902 — 571 ° 24140 = 34 = бед(40902, 24140). История алгоритма Х восходит к трактату АгуаЬЬаг(уа (499 г. и. э.), авторство которого прииадлежит Ариабхата (АгуаЬЬага), жившему в севериой Индии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
