AOP_Tom2 (1021737), страница 182
Текст из файла (страница 182)
Так что иир должен быть более бдительныи. 7. Фактически валс необходимо только 2 двуразрядных значения ( Х„/2'з ~ шой 4; см. П. Е. Кпвз!з, 1ЕЕЕ Тгапз. 1Т-31 (1985), 49 — 52. 3. Неейз, Сгурго!оййа 1 (1977), 20 26, 3 (1979), 83-95. Д. Рид первым начал изучать родственные задачи. (См. также К В!шп, М. В1иш, апй М. 81шЬ, 51СОМР 15 (1986), 364-383: 3.
Воуш, з. Сгурсо!о8у 1 (1989), 177 — 184.) В своей работе Фрииз, Хастед., Кеннан, Лагарнс и Шамир (рпезе, Назсай, Каплан, 1.а8апаз, апс1 Б!запит, 81СОМР 17 (1988), 262 — 280) обсуждают общие технические приемы, используемые в аналогичных задачах. 8. Можно, допустим, генерировать Хсааааее, произведя миллион последовательных вызовов программы, .и сравнивать с точным значением (асеоееооХо + (а'ееезее — 1)с/ (а — 1)) спой т, которое также можно выразить в виде ((а'езеезе(Хо(а — 1) + с) — с) шой (а — 1)т)/(а — 1).
Последний иожно быстро оценить независимым методом (см. алгоритм 4.6.3А), нюсрииер 48271'езеее" шой 2147483647 = 1263606197. Ьольшая часть ошибок обнаруживается, так как рекуррентное соотношение (1) не является самокорректирующимся 9. Значения Ха, Хс,, Лзз не все четные. з + з + 1 — первообразный полинам зео зг (см. раздел 3.2.2); следовательно, существует число 5(з) такое, что Рз(з) з— н з"МС (по иодулю 2 и зсео+аз" +1).
Тогда зРзьс(з) = Р (з)-Х„з~~ — Х„ьзз+Х„ззз'~~+Х ьсоозю = Р„(з) + Х„ьзз(з + з + 1) (по модулю 2), так что результат получается по индукции. сао зг (Ь) Операции "возведение в квадрат' и "умножение на -" в гап зСагС меняют р(з) = хззззз+ .+ хсз+ хе на р(з) и зр(з) соответственно по модулю 2 и з'ее+ зз" +1, твк как р(з) = р(зз). (Мы рассмотрели здесь только младшие двоичные разряды. Другие двоичные разряды преобразуются специальным методом, который стремится сохранить и/или увеличить тот беспорядок, в котором они находятся.) Следовательно, есззи з = (1з,... зсзе)з, то получим 5(з) = (1зозс...з,1)з 2зз. (с) зьоз " = з"о ~ " (по модулю 2 н зшз + зз'+ 1) подразуиевает, что й(з) — и гв 5(з') — пз (по модулю 2'ее — 1) Так как 2зз < 5(з) < 2сее — 2зз, имеем (и — '( > ()с(з) — 5(з')~ > 2~~.
[Этот метод инициализации инспирирован комментариями Р. П. Врента (В. Р. Вгепц ргос. Апзгга!)ап Бпрегсогорп(ег Сопб 5 (1992), 95-104), хотя алгоритм Брента полностью отличается от этого. Вообще, если запаздывание А > 1, если 0 < е < 2' и если отдельный параметр 1 удовлетворяет неравенству 1 + е < Й, зтот метод доказательства показывает, что ~п — и'~ > 2' — 1 с 2' — 1 выполняетсн только тогда, когда (в,з') = (0,2' — 1).] 10.
Следующие операции относятся к упрощенному языку БоЬвес РОНТНАХ, как установлено Аюег(сап )замена! Ееапйагдз 1пз(Нисе, за исключением использования утверждения РАНАИЕТЕН для удобства. ЯОБНОПТ1ИЕ ВКАВНТ(АА,К) ХНРПТС1Т 1ИТЕОЕВ (А-2) 01ИЕИБТОИ АА(ь) РАНАМЕТЕН (КК 100) РАНАМЕТЕВ (11 37) РАНАМЕТЕН (ИМ 2еэ30) СОМНОИ /НЯТАТЕ/ НАКХ(КК) ЯАТЕ /НЯТАТЕ/ ПО 1 Л 1,КК АА(1) ВАКХ(1) 00 2 1 КК+1,К АА(З)=АА(Л-КК)-АА(Л-11) ТР (АА(з) .1т. О) ААС)) "АА(л)+нн СОКТ1КПЕ 00311~. ВАКХ(Л) АА(И+1-КК)-АА(И+1-11) 1Г (ВАКХ(Л) .1 Т. О) ВАКХ(.)) НАИХ(Л) +МН СОИТТКОЕ 00 4 1 Ы+1,КК ВАКХ(1) АА(И+1-КК)-ВАКХ(1-Ы) ХР (ВАКХ(1) .ЕТ, О) ВАКХ(1) ВАКХ(1)+МН СОКТТИПЕ ЕИО БОБНООТ1ИЕ ВКЯТВТ(ЯЕЕП) 1НР1101Т 1КТЕСЕН (А-2) РАНАМЕТЕН (КК 100) РАНАМЕТЕВ (10к37) РАВАИЕТЕН (МН=2ее30) РАВАМЕТЕН (ТТ 70) РАНАМЕТЕВ (ККК=КК+КК-1) 01ИЕИБ10И Х(ККК) СОИИОИ /НЯТАТЕ/ ВАКХ(КК) БАТЕ /ВБТАТЕ/ 1Р (ЯЕЕП .1.Т. О) ТНЕК БЯЕЕП ММ-1-МОП(-1-БЕЕП,ММ) БЕБЕ ББЕЕП МОП(БЕЕП,ИН) ЕКО 1Г ББ ЯЯЕЕО-МОП(БЯЕЕ0,2)+2 (Э-(КК-11))ьММ 20 ВО 1 1-1,КК Х())=ЯЯ ЯБ БЯ+ЯБ 1Г (БЯ .ОЕ.
ИН) ЯБ"ЯБ-МИ+2 1 СОИТТИОЕ 00 2 Л=КК+1,ККК 2 Х(1)=0 Х(2) Х(2)+1 ЯЯ БЯЕЕВ Т ТТ-1 10 00 12 1 КК.2,-1 12 Х()+)-1)-Х()) ВО 13 1 ККК,КК-11+1,-2 1Э Х(ККК-)+2) Х(Л)-НОВ(Х(1),2) ВВ 14 Л ККК,КК+1,-1 1Г (НОВ(Х(Л),2) .ЕО. 1) ТНЕИ Х(Л- (КК-11) ) Х(Ю- (КК-Ы) ) -Х(Л) 1Г (Х(.У-(КК-П.)) .(.Т. О) Х(1-(КК-11.)) Х Х(1-КК) Х(Л-КК)-Х(Ю) 1Г (Х(Л-КК) .1Т. О) Х(1-КК) Х(Л-КК)+НИ ЕИВ ХГ 14 СОИТТИОЕ 1Г (НОВ(ББ,2) .ЕО.
1) ТИЕИ 00 16 3 КК,1,-1 16 Х(3+1) Х(Л) Х(1) Х(КК+1) 1Г (НОВ(Х(КК+1),2) .ЕО. 1) ТНЕИ Х(11+1) Х(11+1)-Х(КК+1) 1Г (Х(Ы +1) .11. О) Х(11 +1!"Х(Ы+1)+НН ЕИ) ХГ ЕИВ 1Г 1Г (ББ .ИЕ. О) ТНЕИ БЯ БЯ/2 ЕВЯЕ Т Т-1 ЕИВ 1Г ТГ (Т .ОТ. О) 00 ТО 10 00 20 Л 1,11 БХИХ(Л+КК-11)=Х(1) ВО 21 1=11+1,КК 21 КАИХ(Л-ьь)=Х(Л) ЕИВ 11. Лрифьгетика с плавающей точкой на операндах с 64-мя двоичными разрядами соответствует А)(Я)/!Е:ЕЕ Ясапбагй 764 и позволяет вычислять У„= (б'„гее -Уь зг) шод 1 с прекрасной точностью для дробей ()„, которые являются целыми кратными 2 Тем не менее следующая программа использует адднглиеиое рекуррентное соотношение (7, = (() -юо + У ьм) шог) 1 для целых кратных 2 ы, так как конвейерные компьютеры могут вычитать целую часть более быстро, чем выполнять условный переход по знаку промежуточного результата.
Теория из упр. 9 применима также к втой последовательности. Основной новой идеей программы гоп)" з(аг( является хранение копии и( младших значащих двоичных разрядов дробей в в. Перевод на язык программирования РОКГКЛХ, подобно операциям из упр. 10, генерирует такие же числа, как и программа на языке ЬЬ Ябетспе КК 100 /» длинное запаздывание «/ Ебегппе ЬЬ 37 /» короткое запаздывание »/ Ебеутпе иоб вшп(к,у) (((х)+(у))-(гпС)((х)+(у))) /» (к+у) иод 1.0 »/ бопЫе гап п[КК]; /» состояние генератора ° / чопб галу актау(бапЫе ааП,>пс и) ( /« аа присвоить и случайнмх дробей «/ гебсзсег (пс >,5; уаг Ц=О;)<КК;)++) ааЦ]=гап в[5); Хат (;)<п;)++) ааЦ] пай вшп(аз[5-КК],ааЦ-ЬЬ)); бог (>=О;><ЬЬ;г++,3»+) гап п[с] =изб зпи(аз[5-КК), ааЦ-ЬЬ] ); Хог (;1<кк;1++,5+») гап и [1] =изб зшп(ааЦ-КК],гап и [1-ЬЬ] ); ) Вбег(пе ТТ 70 /« гарантирует разделение потоков */ Ябеу1пе 1в обб(з) ((з)01) чогй твпг зсагс(1апй *ееб) ( /» сделать до использования гапт аггау »/ гебсзеег 1пС С,з,); бапЫе з[КК+КК-1],в)[КК+КК-1]; бовЫе п1р=(1,0/(1Ь«30))/(1Ь«22); / ° от 2 к -62 «/ бовЫе аз=2.0»п1р»(веед«2); уог Ц=О;)<КК;)++) пЦ]=вв; в1Ц]=0.0; /» инициализация буфера «/ вв+=зв; гг (вв>=1.0) вз- 1.0-2»в1р; /«циклический сдвиг на Б1 дваичний разряд «/ Хог (;)<КК+КК-1;)++) вЦ)=в1Ц]=0,0' п[1)+=п1р;п1[1]=п1р; /» получаеи в[1) (и только п[1]) "нечетное»»/ 3 вееб; с=тт-1; затте (с) ( Г Ц=КК-1;)>О;)--) пЬЦ+)]=ЫЦ].пЦ+))=вЦ]; /« "возведеаие в квадрат" »/ У Ц=КК+КК-2;5>КК-ЬЬ;)-=2) п1[КК+КК-1-)]=О.О,п[КК+КК-1-)) п[5]-п1Ц]; Уог Ц=КК+КК-2; ) >=КК; ) — ) > К (п1 Ц] ) п1 Ц-(КК-ЬЬ)]=а1р-в1Ц-(КК-ЬЬ)], и Ц-(КК-ЬЬ)]=изб зшв(зЦ-(КК-ЬЬ)],пЦ)); п1Ц-КК]=п1р-п1Ц-КК].пЦ-КК) =иоб вшп(пЦ-КК),пЦ) ); 11 (св оба(з) ) ( /» "унновение на к" »/ Хог Ц=КК;5>0;5 — ) п1Ц)=з1Ц-1],пЦ]=вЦ-1]; п1[0) п1[КК],в[0]=п[КК]; /» цнклнческяй сдвиг буфера »/ гй (п1[КК)) в1[ЬЬ]=п1р-п1[ЬЬ],п[ЬЬ]=иоб вшп(п[ЬЬ],п[КК)); ) ЬХ (з) в»=1; е1*е С ) сот () =0;) <11; )++) тал и[)»КК-сь) =и[)); тот (;)<КК;)++) гав и[)-Щ =и[)); насл() ( ге81ксег тпс н; йоиб)е а[2009); /» эпенентарннй критерий »/ гэпг эсагс(310952); тот (н=О;и<2009;н++) гвос аггау(а,1009); ргспсг("7,.2011п", тая и[0)); /» 0.27452626307394156766 »/ ганг всагс(310952); уог (н=О;и<1009;н++) гап1 аггау(в,2009); ргтпсг("7,.2011п".
гал и[0)); ) /* 0.27452626307394156768 »/ 12. Простой линейный конгруэнтный генератор, подобный (1), не подходит, так как гп чересчур малб. Хороший результат возможен при комбинации трех (не двух) таких генераторов с множителнми и модулями (157,32363), (146,31727) и (142,31657), как советует П. Лекуер (Р.
[/Есиуег, САСМ 31 (1988), 747-748) Тем не менее лучшим методом ивляется использование программ иа нзыке С гоп аггоу и гоо эсаг( со следующей заменой, чтобы сохранить все чис.за в области '1опб' становятся 'тпС', 'НН' определяется как '(10«15) ' и тип переменной щ должен быть ипв18пей гпс. Тогда генерируются целые числа, содержащие 15 двоичных разрядов, нз которых можно использовать все двоичные разряды. Начальное значение сейчас ограничено областью (О .32765] "Программа элементарной проверки" напечатает Х»еоэх эооэ = 9387 при заданном начальном значении 12509. 13.
Программа вычитания с заимствованием очень похожа на программу гоп агга»9, но работает медленнее, поскольку сохраняет содержимое. Как в упр. 11, арифметику с плавающей точкой можно использовать с совершенной точностью. Это позволяет гарантнровать "непересеченне" последовательностей, полученных от различных начальных значений э путем инициализации генератора с (-и)-м элементом последовательности, где и = 2"е'. Этого требует вычисление Ь" шой (Ь» — Ь' х 1). Возведение в квадрат числа с основанием Ь по пюй Ь вЂ” Ь т. 1, тем не менее, значительно сложнее, чем аналогичная олершгия в программе гоп эгогй и для Ь оно практически выполняется за приблизительно Ь 'е операций се вместо О()г). Оба метода, вероятно, практически генерируют последовательности одинакового качества, когда у них приблизительно те же самые значения )с.
Единственным различием между ними является лучшее теоретическое обоснование и, возможно, огромный период метода вычитания с заимствованием, анализ генератора Фибоиаччи с запаздыванием менее полный. Опыт показывает, что можно было бы не уменьшать значение Ь в методе вычитания с заимствованием только из-за его теоретических преимуществ. Когда всг это сказано и сделана, генератор Фибоначчи с запаздывание»» кажется предпочтительнее с практической точки зрении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
