AOP_Tom2 (1021737), страница 106
Текст из файла (страница 106)
л. При наличии большего накопителя можно было бы увеличить количество шагов, на которых вычисления выполняются с однократной точностью. Из примера видно, что в один сложный шаг объединяются только пять циклов алгоритма Евклида, а если бы, скажем, размер слова равнялся десяти разрядам, можно было бы объединить в один шаг до двенадцати циклов. Из результатов, доказанных в разделе 4.5.3, следует, что на каждой итерации число циклов с многократной точностью, которые можно заменить циклами с однократной точностью, пропорционально размеру слова, используемому в вычислениях с однократной точностью. Метод Непера можно сформулировать следующим образом. Алгоритм Ь (Алгоритм Евклида длл больших чисел). Пусть и и е — представляемые с однократной точностью неотрицательные целые числа, такие, чта и > е.
Этот алгоритм вычисляет наибольший общий делитель чисел и и е, используя вспомогательные р-разрядные переменные й, е, А, В, С, Р, Т, о, которые представлены с однократной точностью, и вспомогательные переменные 1 и ш, которые представлены с многократной точностью. Ь1. [Начальная установка.] Если число е достаточно мало, чтобы быть представленным в формате с однократной точностью, то ясб(и, е) вычисляется по алгоритму А, и на этом вычисления заканчиваются. В противном случае обозначим р ведущих разрядов числа и через й, а соответствующие разряды числа с— через О.
Другими словами, если используется представление чисел в системе счисления по основанию Ь, та й г — [и/Ьь) и О +- [е/Ьг), где 1с — наименьшее возможное число, удовлетворяющее условию й < Ьг. Присвоить А +- 1, В о- О, С г- О, Р +- 1. (Эти переменные представляют коэффициенты в (28), где (29) и = Аио+Вео и е = Сио+Рео в равносильных операциях алгоритма А над числами с многократной точно- стью. Кроме того, е' = О+Р, и" = й + А, е" = й + С (30) и' = й+В, в обозначениях рассмотренного выше примера,) Ь2.
[Проверить частное.) Присвоить о+- [(й+А)/(й+С)). Если о ф~ (й+В)/(О+Р)), то перейти к шагу Ь4. (На этом шаге проверяется выполнение условия д' ф о" в обозначениях того же примера. В процессе вычислений на этом шаге при некоторых обстоятельствах, когда й = Ьг — 1 и А = 1 или когда О = Ьг — 1 н Р = 1, может возникнуть переполнение при выполнении операций в формате с однократной точностью.
В силу равенств (ЗО) всегда будут выполняться условия 0 < о+С <Ьг, 0<О+Р<Ь". 0 <й+А < Ь", 0<и+В <Ь, (31) Может оказаться, что выполнится одно из равенств О + С = 0 и е + Р = О, но не оба одновременно. Поэтому попытка деления на нуль на этом шаге означает "Перейти непосредственно к шагу Ь4".) Ь3. [Имитация алгоритма Евклида.) Присвоить Т +- А — оС, А о- С, С ь- Т. Т г-  — дР, В г- Р, Р +- Т, Т +- й — ое, й о — е, е г — Т и возвратиться к шагу Ь2. (Эти вычисления с однократной точностью равносильны операциям с многократной точностью в процедуре (28) с учетом (29).) Ь4. [Шаг, на катарам выполняются вычисления с многократной точностью.) Если В = О, то, используя деление с многократной точностью, присвоить | +- и шаб е, и +- е, е о — Ь (Это может случиться толька тогда, когда с помощью операции с однократной точностью нельзя моделировать операцию с многократной точностью. Отсюда следует, что алгоритму Евклида требуется очень большое частное, что может произойти крайне редко.) В противном случае присяоить г с — Аи, Ь г — г+ Ве, ш г- Си, ш +- ш + Ре, и +- Ь е +- ш (выполняя непосредственно операции с многократной точностью).
Возвратиться к шагу ЬЬ 1 С учетом неравенств (31) в процессе вычислений значения величин А, В, С, Р представляются с однократной точностью. Для реализации алгоритма 1, требуется несколько более сложная программа, чем для алгоритма В, но при оперировании большими числами этот алгоритм на многих компьютерах выполняется быстрее. Подобным образом можно ускорить выполнение бинарного алгоритма В в завершающей стадии (см. упр. 38). Преимущество алгоритма Ь заключается в следующем: он определяет последовательность частных, получаемых при выполнении алгоритма Евклида, что используется в многочисленных приложениях (см., например, упр.
43, 47, 49, упр. 51 в разделе 4.5.3, а также упр. 4.5.3 — 46). ~А.нализ бинарного алгоритма. В заключение этого раздела для обоснования установленных ранее формул проанализируем время выполнения алгоритма В. Выясняется, что точно описать поведение алгоритма В крайне затруднительно, но можно начать анализ этого алгоритма с его приближенной модели. Предположим, что числа и и е нечетны, и > е и (1йи) =т, (18е1 =и. (32) (Таким образом, и является (т+ 1)-битовым числом, а е — (и+1)-битовым числом.) Рассмотрим выполнение в алгоритме В цикла "вычитание и сдвиг", т. е.
операцию, которая начинается на шаге Вб, а прекращается после окончания выполнения шага В5. Каждый цикл "вычитание и сдвиг" при и > е вычисляет разность и — е и сдвигает эту величину вправо до тех пор, пока не будет получено нечетное число и', которое замещает число и. Если входные числа случайны, можно ожидать, что примерно в половине случаев и' = (и — е)/2, примерно в четверти случаев и' = (и — е)/4, примерно в одной восьмой случаев и' = (и — е)/8 и т. д. Получаем (18и'1 = т — й — г, (33) где к †чис разрядов, на которые было сдвинуто вправо число и — е, а г есть (!8 и) — (!8(и — е)! — количество битов, потерянных слева во время вычитания числа е из числа и.
Заметим, что г ( 1 при т > и+ 2, а г > 1 при т = и. Взаимосвязь между Ь и г довольно беспорядочная (см. упр. 20), однако Ричард Врент (ШсЬагд Вгепг) нашел изящный способ анализа поведения приближенной модели алгоритма, положив и и е достаточно большими, такими, чтобы отношение е/и имело непрерывное распределение при дискретном изменении Ь. [См.
А!8ог11Лшэ апд Сошр!ех1гу, е611еб Ьу Л. Г. ТгацЬ (ь1ен Уаттс: Асадепис Ргеээ, 1976), 321 — 355.) Предположим, что и и е — большие целые числа, возможно, случайные, но обязательно нечетные и их отношение подчинено определенному закону распределения. Тогда на шаге В6 младшие значащие биты величины Г = и — е могут быть случайными, но величина Г будет четной. Следовательно, 1 будет нечетно кратным 2" с вероятностью 2 ь; зто приближенная вероятность того, что в цикле "вычитание и сдвиг" потребуется выполнить й сдвигов вправо.
Другими словами, получено подходящее приближение, описывающее поведение алгоритма В при сделанных предположениях о том, что переход от шага В4 к шагу ВЗ всегда будет происходить с вероятностью 1/2. Пусть С„(х) — вероятность того, что пнп(и, е)/шах(и, е) будет > х после выполнения с учетом этих предположений п циклов "вычитание и сдвиг". Если и > е и если выполнено точно й сдвигов вправо, то отношение Х = и/п изменится на Л' = ппп(2"с/(н — и),(и — с)/2ьв) = ш1п(2ьХ/(1 — Х), (1 — Х)/2 Х). Таким образом, неравенство Х' > т будет справедливо тогда и толька тогда, когда 2ьХ/(1 — Х) > х и (1 — Х)/2"Х > х, а это то же самое, что и 1 1 — < Х < —.
1 + 2 "/х 1 + 2" х (34) Поэтому С„(х) удовлетворяет интересному рекуррентному соотношению С„ег(х) =~2 ~(С„( „) — С„( „)), (35) где Сэ(х) = 1 — х при 0 < х < 1. Проведенные вычислительные эксперименты показали, что С„(х) быстро стремится к предельному распределению С, (х) = С(х) несмотря на то, что формальное доказательство сходнмости представляется неочевидным. Будем полагать, чта существует функция распределения С(х). Тогда она удовлетворяет уравнению С(х) = ~~г 2 ~(С( ) — С( „)) при 0 < х < 1; (3б) й>1 С(0) = 1; С(1) = О. (37) Пусть (38) тогда С(х) — Я(1/х) Я(х) (39) Естественно определить С(1/х) = — С(х), (40) С(х) = а(х) 18х+ г8(х) + ~~~ (угг,(х) сов 2ит18х+ бггг(х) э1п 2хт18х), в~=1 5(х) = Л(х) 18х+ д(х) + ~~г (а~(х) соэ2ггт18х+ тт(х) эгп 2пт!8х), ггг= 1 Р(х) = С(1 + х) = Гггх + рэх + рэх + ргх + рэх + рбх + (41) (42) (43) так что уравнение (39) справедливо для всех х > О.
Поскольку х изменяется от 0 до ао, 5(х) увеличивается от 0 до 1. Следовательно, С(х) уменьшается ат +1 до -1. Конечно, прн х > 1 функция С(х) перестает быть вероятностью, тем не менее она имеет смысл (см. упр, 23). допустим, что имеются степенные ряды а(х), )У(х) ут(х) бггг(х)~ Л(х)~ И(х)~ а,„(х), т (х) и р(х), такие, чта Рнс. 10. Предельное распределение отношений в бинарном алгоритме вычисления наи- большего общего делителя. поскольку можно показать, что этим свойством при и > 1 обладает рещение С„(х) уравнения (35) (см., например, упр. 30). Эти степенные ряды сходятся прн )х~ < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
