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