Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 57
Текст из файла (страница 57)
Таким образом, (т/тл = (.игиг., )га, если положить 11е = У и У„1ОУ„! !пот) тп = 100„! — ти . Неформально цифры 1/т являются начальными цифрами 10» шос) тл при н = 1, 2,.... Последовательность, в конце концов, периодическая; ояа совпадает с начальными цифрами 10 " шот) тв, взятыми в обратном порядке, Таким образом, можно вычислять их, как в (с). Точное доказательство, конечно, предпочтительнее неформального. Пусть Л вЂ” наименьшее положительное число с 10" ш 1 (по модулю тл). Определим х»»» х»и»ез, Ь = Ь» и»е ы Х» = Х»»е з для всех и < О.
Тогда рекуррентное соотношеняе лдя х, Ь и Х» в (с) справедливо для всех целых н. Если Уе — — 1, то 11 = Х» и и» = х следовательно, 999999900" шот19999998999 9999998999 = (,х» !х»-гх»-з... )ге. (е) Пусть ш — длина компьютерного слова ш. Используем рекуррентное соотношение х»»з (х -г — х» ! — Ь ) шот) ш = х»-г — х» ! — Ь + итЬ +г, где 0 < 1 < Ь и Ь большое. Тогда (.х , тх -гх -з ..) = Л /т, где тн = шг — ш' — 1 и Л +! = (шз ' — ш! ')Х шопот. Соотношение Л» = (х !... х„-з) — (х» !... х„-!) + Ь„ справедливо для и > 0; величины х г, ..., х г и Ье должны быть такими, что О < Хе < нь Такие генераторы случайных чисел и подобные им (см, свел!ующие упражнения) были введены в работе С. Мвгиабба аш1 А.
Евшая, Авпл1з о! Арр1гет( Ргобабг1ггу 1 (1991), 482-480. Авторы назвали свой метод емчютюиием с заимстлеоеаиием. Они исходили нз представления с основанием и! дробей со знаменателем тв. Связь с линейной конгруэнтной последователъностью была замечена Шу Тезука (ЗЬв Теввйа) и детально проанализирована в работе Техвйа, 1'Есиуег аэб Соэгвге, АСМ згапв. Мо!Ы!лб алг( Сотр0201 31шп13!!Ол 3 (1993), 315-331.
Длина периода обсуждалась в упр. 3.2.1.2-22. 13, Для умножения на 10 сейчас требуется предсвшлеиие добавленных цифр в виде ош- рицаКЕЛ их дОпОлнЕния. Длв ЭтОгО УДОбно представить число так, чтобы последние три цифры заменялись отрицанием ик дополнений, например 987б543210 = (9575544790)ю. Тогда на 10-и шаге (хэ .
Хзх22190) и равно (ХО .. Хэх йътойэ)10, где х' = хэ — х3. Аналогично (ХО... хзх2х190) и, деленное на 10, равно (хохо... х0хлх2х1)10, где хп = хо — хз, Из рекуррентного соотношения Хп (Хп-3 Хп 10 Ьп 1) Шоо 10 х» 3 Х» 10 Ьп 1 + 10Ь» следует 3999999101» шоб 9999999001 = Хп, где Лп (хл-!Хл-2Х»-Охл-Охл-Охп-Охл-!Х»022»»1хп)10+ 10006»+3 (3» !х» 2 Хп 10)10 (Хп 1Хп-2Х»-3)10+ Ь». Когда за основание системы счисления вместо 10 принимается ш, находим, что обратная степень 00 по модулю ю" — э/ + 1 порождена рекуррентным соотношением хп пп (х ! — х 0 — Ь )шо0(ю =х ! — хп 3 — Ьп+мЬ ь! (таким же, как в упр. 12, но Ь и 1 меняютсл местамн).
14. Неболыпое обобщение. Дэя любого 6, меньшего или равного длине слова ю, можно эффективно осуществлять деление на Ь по модулю Ь -Ь'х1. Таким образом, рекуррентное соотношение для х почти так же эффективно при 6 < ю, как н при Ь = ю. Сильное обобщение. Рекуррентное соотношение )а1Х -1+" +ООХ 3+0»! х =(01хп 1+ .+а3х !+с»)пик1Ь, с»01 — ~ Ь эквивалентно Хп = Ь 'Хп 1 шо!((Ш) в том смысле, что Х„/)т! = (.Хп !хл-2 ° . )ь, если определить ш и Л следующим образом: =,»' ° ..
„Ь-!, 2. (2 ПЛ.- . *.,) ° .)!»Л 1 Ъ! 1 Начальные значения х 1... х 0 и со должны быть выбраны так, что 0 < Хо < (т(! тогда получим хп = (ЬХ»01 — Хп)/)ш) для и > О. Значения х1 для / < О, которые появляются в ферМУЛЕ Л /1Ш! = (.Хл-1Х -2.. )Ь, МОЖНО ПрОСтО раССМатрИВатЬ, КаК Х.~~ОЫ Гдс Ь Ш 1 3 (по модулю н1). Эти величины могут отличаться от заданных вначале чисел х-1,..., х 1,. Цифра переноса сп удовлетворяет неравенствам Я,шш(О,О1) < с < ~ и!ах(О,а1), если начальный перенос 00 лежит в тех же пределах. Представляет особый интерес случай, когда гл = 6" + Ь! — 1, для которого а, 811 + 613, поскольку он легко вычисляется. Марсалья и Заман назвали его генератором СУ»!МНРООО»и» С НСРЕНОСаи: Х» = (Хп-1+Хл-3+0») ШООЬ = Хл-1+ Хп-3+ Сп 60»+1 Другой привлекательной лотенциалъной возможностью является исполъзование й = 2 в генераторе с, скажем, Ь = 23' и н1 = 55430Ь3 + Ь вЂ” 1.
Этот модуль т является простым числом, н длина периода оказывается равной (ш — 1)/2. Спектральный тест из раздела 3.3.4 показывает, что интервал между уровнями хороший (большие значения и), хотя, конечно, множитель Ь 1 плохой по сравненню с другнмн множителями для этого значения модуля т. В упр. 3.2.1,2-22 содержится дополнительная информация о модулях, позволяющих получить чрезвычайно длинные перноды в методах "вычитание с заимствованием" н "суммирование с переносом". РАЗДЕЛ 3.2.1.2 1. Согласно теореме А длина периода равна т (см. упр. 3). 2. Да, нз этих условий следует, что выполняются условия теоремы А, гак как единственным простым делителем 2' является 2 и любое нечетное число является отнсснгельно простым с 2'. (На самом деле условна упражнения являются невбхадкээммп н достаточными.) 3.
Согласно теореме А требуется, чтобы а ш 1 (по модулю 4) и а ш 1 (по модулю 6). По закону Р нз раздела 1.2.4 это эквиваэентно тому, что а ш 1 (по модулю 20). 4. Из теоремы А следует, что Х,.-1 ш 0 (по модулю 2' ') (случай, когда 1п = 2' '). Используя также теорему А прн т = 2', получим, что Хы-~ ш 0 (по модулю 2'). Отсюда следует равенство Хз.-1 = 2' '. Вообще говоря, можно использовать формулы 3.2.1-(6) для доказательства того, что вторая половина периода, по существу, подобна первой половнне, так как Х„ээ,-~ = (Х„+ 2' ') шо62'. (Четверти также подобны; см.
упр. 21.) 6. Необходимо, чтобы выполнялось следующее соотношение а ш 1 (по модулю р) для р = 3,11,43,281,86171. По закону Р нз раздела 1.2.4 это эквивалентно тому, что а ш 1 (по модулю 3 11 43 281 86171). Итак, единственным решением будет ужасный множитель а = 1, 6.
(См. предыдущее упражнение.) Из подобия а ш 1(по модулю 3 7 11 13 37) следует, что решением будет число а = 1 + 1111118 для 0 < А < 8. 7. Воспользуемся обозначениями нз доказательства леммы (4. д является наименьшим значением, прн котором Х„.~э ж Хгл также оно является наименьшим значением, прн котором У„.„х = 1;, и Е„.~э = Е„. Таким образом, показано, что;и = гпах(дь,,.,1н).
Нанболыпнм нз возможных значенкй д есть шах(ем..., е~), но никто не пытается достичь его. 8. Легковндеть, чтоаз ш 1(по модулю 8) на ш 1(по модулю 16), а ш 1(ио модулю 32) н т. д. Если ашо64 ы 3, то а — 1 — удвоенное нечетное число, Таким образом, (аэ — 1)/(в — Ц ш 0 (по модулю 2') тогда н только тогда, когда (аэ — 1)/2 ш 0 (по модулю 2'+'/2), что справедэиво. 9.
Представить выражение для Х, в терминах У„н упростить его. Если Хо по модулю (шоб) 4 ы 3, формулы из упражнения неприменимы; однако, онн применимы к последовательности о = (-Х ) шоб 2*, которая, по существу, ведет себя так же. 10, Только для т = 1, 2, 4, р' н 2р', для нечетных простых р, Во всех других случаях результат теоремы В является усовершенствованным вариантом теоремы Эйлера (упр. 1.2.4-28). 11.
(а) Каждое число х + 1 нли х — 1 (но не оба) кратно 4. Таким образом, х ~ 1 = 027, где о — нечетное число я / > 1. (Ь) При данных обстоятельствах / < е п, значит, е > 3. Пслучнм шх ш 1 (по модулю 27) н шх ж 1 (по модулю 27+') н / > 1. Отсюда, э.-г-1 э э'"г применяя лемму Р, находим, что (шх) ш 1 (по модулю 2'), тогда как х (жз)~ ш 1 (по модулю 2').
Таким образом, порядок является делителем 2' 7, но не является делителем 2" ~ '. (с) 1 имеет порядок 1; 2' — 1 — порядок 2, максимжп ный период, где е > 3, равен, следовательно, 2' з,и для е > 4 необходимо, чтобы / = 2, т, е. х щ 4 х 1 (по модулю 8). 12. Если к — делитель р — 1 и если а щ 1 (по модулю р), то по лемме Р о" щ 1 (по модулю р'). Аналогично, если аг ' щ 1 (по модулю рт), находим, что ащ не* щ 1 (по модулю р'), Таким образом, в данных случаях а не является первообразным элементом.
Обратно, если аг ' х 1 (по модулю рт), то по теореме 1.2.4Г и лемме Р имеем, -ю *-1 что а"* гж х 1 (по модулю р'), но ащ н" щ 1 (по модулю р'), поэтому порядок является делителем (р — 1)р' ', ио не (р — 1)р' ~; следовательно, он имеет вид кр', где й делит р — 1. Но, если а является первообразным элементом по модулю р, конгруэнтность г *-' о~э* щ а~: — 1 (по модулю р) влечет к = р — 1.
13. Предположим, а щобр Ф О, и пусть Л вЂ” порядок а по модулю р. По теореме 1.2.4Р Л является делителем р — 1. Если Л < р — 1, то 6 имеет простой множитель (р — 1)/Л. 14. Пусть О < к < р. Если а" ' щ 1 (по модулю рз), то (а + Ар)" ' щ аг ' + (р — 1)о" зйр (по модулю рз) и это выражение ф 1, так как (р — 1)а" ~я не кратно р. Из упр. 12 следует, что а + йр — первообразный элемент по модулю р'. 15. (а) Если Л~ = р",, . р" ,и Лз = р/'...
р(', положим к~ = рф... рь и кз = р"'... р~', где если е, < /1, если ез > /у и /Ь О, и 5,=/;, д.=е, 9,=0 Тогда а",' и азз имеют взаимно простые периоды Л~/к~ и Лз/кг соответственно. К тому же (Л~/к~)(Лз/кз) = Л. Таким образом, достаточно рассмотреть случай, когда Л~ и Лз— взаимно простые числа, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
