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