Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 59
Текст из файла (страница 59)
15.) (Ь) Подчеркнутые числа — это Ъ ]/] после шага В2. В этом случае выход значительно лучше ахала; он привносит повторяющийся цикл длиной 40 после 46 шагов: 236570 05314 72632 40110 37564 76025 12541 73625 03746 (3017о 24061 52317 46203 74531 60425 16753 02647). Можно легко найти цикл, применяя методы нз упр. 3.1-7 к приведенной выше таблице до повторяющихся столбцов. 4. Байты младшего порядка многих случайных последовательностей (например, линейная конгруэнтиая последовательность с хп = длина слова) намного менее случайны, чем байты высокого порядка (см. раздел 3.2.1.1).
5. Эффект рандомизации будет сведен к минимуму, потому что Щ всегда будет содержать числа из определенного интервала. а именно — //я < )х[/]/хп < (у + 1)/)х, Однако использование подобных подходов вполне допустимо. Можно положить 1'„= Х„1 или выбрать / из Л„, извлекая некоторые цифры из середины числа, а не из его левой части. Никакое из этих предложений не будет удлинять период, как это делает алгоритм В. (В упр. 27 показано, однако, что алгоритм В необязательно увеличивает длину периода.) 8.
Например, если Х„/ха < -', то Хаю = 2Х . 7. (Мантель В. ]%. Маисе!, Ххени АгсЫе/ тоог 'хххякппх(е (2) 1 (1897), 172-184.] 00...01 00...01 00...10 00... 10 Последовательность значений Х схановится такой; 10...00 СОИТЕМТЕ(А) СОМТЕИТ3(А) 8. Можно предположить, что Хе = 0 и т = р', как и при доказательстве теоремы 3.2.1.2А, Сначала предположим, что последовательность имеет длину периода р'. Отсюда следует, что период последовательности по модулю р~ имеет длину рх для 1 < / < е, ииаче иекоторые вычеты по модулю рг никогда ие будут встречаться.
Ясно, что с не кратно р. с другой стороиы, Х» должно быть кратно р. Если р < 3, то легко доказать необходимость условий (ш) и (!у) методом проб и ошибок, поэтому можио предположить, что р > 5, Если з( щ 0 (по модулю р), то г(хз + ах + с ш 4(х + а~ )з + с~ (по модулю р ) для некоторых целых щ и с. и для всех целых х.
Этв квадратичная форма принимает одии и те же значения в точках х и — х — 2ам поэтому оиа ие может принимать все значения по модулю р'. Следовательно, Ы щ О (по модулю р) и, если а щ 1, выполнялось бы равенство г(х + ах + с щ х (по модулю р) для некоторых х, а это противоречит тому факту, что последовательность по шоб р имеет период длииой р, Чтобы показать достаточносп, условий, можно воспользоваться теоремой 3.2.1.2А и рассмотреть несколько тривиальных случаев, когда гл = р', где е > 2. Если р = 2, то ясно, что Х, з щ Х р 2 (по мщ!Улю 4), если р = 3, получим Х +з щ Л» — г(+ 3с (по модулю 9), используя (!) и (б), Для р > 5 можно следующим образом доказать, что Х рр щ Л» + Рс (по молУлю Рз).
ПУсть е( = Рг. а = 1 + Рз. Тогда, если Л„щ сп + Р)'» (по модУлю Р ), необходимо полУчить 1„4~ щ пзсзг + поз + 1'„(по модУлю Р); поэтомУ 1';, = (')2с~г+ („")(с г ч- сз) (по модулю р). Таким образом, 1"р шобр = О, и слзотношение доказано. Сейчас можно доказать,что последовательность (Х„) целых чисел, определенная в "указании", удовлетворяет соотношению х„ррг щ х +грг (по модулю рг '), и > О, лля некоторых 1 с г шоб р ф О и для всех у > 1. Этого достаточно для доказательства, что последовательность (Х„шод р" ) имеет период длиной р', если длина периода является делителем р'„ко ие делителем р' .
Соотношение, приведенное выше, уже было устаиовлеио для у = 1, и лля 1 > 1 оно может быть получеио по индукции следующим образом. Пусть х„. „г == х„+ ерг + л„рур' (по модулю рге~), тогда из квадратичиого закова дтя генерирования последовательности с 4 = рг, а = 1 + рз следует, что Х»е~ щ 2щпс+ зг+ 3» (по модулю р). Поэтому 3»+р и а (по модулю р). Следовательно, Х„„„рг щ Л + (г(гр~+ З„р~~ ) (по модулю р~~ ) для )г = 1, 2, 3, .... Если положить теперь й = р, то на этом доказательство будет завершено, Заме»акис. Если г(х) -- поливом степени, более высокой, чем 2, и Х .~г = 1(Х ) анализ будет несколько сложнее, хотя можно использовать тот факт, что 1'(ш + р ) = з р (пз) + р 1 (т) р р 1 '(т)/2! +, лля доказательства того, что многие полиномиальиые последовательности дают максимальный период.
Например, Ковэю (Соуеуоп) доказал, что период разек ти = 2', если 1(0) нечетко, ~'(1) щ 1, ~р(з) щ 0 и Ду + 1) = — Д1) + 1 (по модулю 4) для 1 = О, 1,2, 3. (5заобез !л Арр)мд Мага, 3 (РЬ!!аг)е!рЬ!а: 9!АМ, 1969), 70-111.) 9. Пусть Х = 4г' + 2; тогда последовательность 1' удовлетворяет квадратичному рекурреитному соотношению У;р~ — — (4Уз + 31' + Ц шог! 2' 10. С»рчаа 1: Хз = О, Хз = 1; следовательно, Л щ г',. Ищем наименьшее и, для которого Г» щ 0 и Б,е~ щ 1 (по модулю 2'). Так как Кз» = Г (Г -з + Г»»з), Гг .рз = 'г" + ~~и-з найдем индукциейпо е, что для е > 1 Газ.-~ щ О и Ез,з.-~.р, ш 2'+1 (по модулю 2' ).
Это означает, что период является делителем 3. 2' ~, но не 3 2" з. Следовательно, период равен либо 3. 2' ~, либо 2' '. Но гз,-з — всегда нечетное число (так как только гз„— четное). Случай 3: Хе = а, Хз = Ь. Тогда Х» ш ар з + Ьг». Нужно найти наименьшее положительное и, такое, что а(р'„~.1 — Е ) + Ьр'„ш а и аг'„+ Ьг' гл ш Ь.
Это влечет, что (Ь вЂ” аЬ вЂ” а )р'„ш О, (Ь вЂ” аЬ вЂ” а~)(г эз — 1) ш О. И Ь вЂ” аЬ вЂ” а нечетно (т. е. оно простое относительно зп). Итак, условие эквивалентно тому, что г» ш О, Г„~., = 1. Метод определения периода Е для любого модуля впервые был приведен в статье Д. Д. Волла (О. О. ЪЫ1, АММ 67 (1960), 525-532). Другие факты относительно последовательности Фибоначчи по модулю 2' найдены Б, Йенссеном (В.
Лапззоп, Капе(ош НашЬег Седегасогз (3цлсИю!ш: А!шйтйз Ьс айве!1, 1966), Яесз!оп ЗС1). 11. (а) легко видеть, что г = 1+/(х)а(з)+р'е(х) для некоторых а(х) и е(г), где е(х) ш 0 (по модулю /)(г) и;э. По биномивльной теореме хлр = 1+ р'+'е(х) + р" +' е(х)'( — 1)/2 плюс следующие члены, конгруэнтные нулю по модулям /(г) и р'э~. Так как р* > 2, то хл" и 1+р'~'е(г) по модулям /(г) и р'~ . Если р'.'и(х) ш 0 по модулям /(х) н р'~~, должны существовать полииомы а(х) и Ь(х), такие, что р»ы(е(г) + ра(г)) = /(г)Ь(г). Поскольку /(О) = 1, получаем, что Ь(г) кратно р'е' (по лемме Гаусса 4.6.1О). Отсюда е(х) ш 0 по модулям /(х) н р.
В итоге получено противоречие. (Ь) Если хл — 1 = /(х)а(х) +р»и(г), то О( ) к( )/(х~ — 1) + р'о(х)//(г)(г~ — Ц; следовательно, А„гл ш А„(по модулю р') для больших и. Обратно, если (А„) обладает последним свойством, то лр(х) = а(х) + е(х)/(1- хл) + р'Н(г) для некоторых полиномов и(х) и е(г) и некоторого степенного ряда Н(х'), таких, что ряд и полиномы ил~еют целые коэффициенты, Отсюда следует равенство 1 — х" = и(г)/(г)(1 — х") + е(х)/(г) +р'Н(г)/(г)(1 г ): и Н(х)/(х)(1 — г ) является полиномом, так как другой член равенства — полинам, (с) Достаточно доказать, что неравенство Л(р');4 Л(р'~') влечет такие соотношения Л(р'+') = рЛ(р') ф Л(р'»з).
Из (а) н (Ь) следует, что Л(р'"з) уе рЛ(р') и что Л(р»лз) является делителем рЛ(р'), но не Л(р»). Следовательно, если Л(р*) = р!д, где 9 пи»1 р р О, то Л(р'е') должно равняться р~+'а, где 3 — делитель д. Но сейчас Х„эргрз ш Х„(по модулю р'); значит, рГ+'Ы кратно рГ9 и 3 = ф [Замечание. Предположение о том, что р' > 2„ необходимо; например, если аз = 4, аз = -1, Ь = 2, то (А„) = 1, 4, 15, 56, 209, 780, ...; Л(2) = 2.
Л(4) = 4, Л(3) = 4.! (д) 9(г) =Хе+(Хз — азХе)х+ +(Хл з -азХл з — азХз-з —" — ал-1Хо)гл '. (е) Утверждение (Ь) можно обобшнть лля б(г) = 9(х)//(г); следовательно, предположение, что длина периода равна Л, влечет то, что 9(х)(1 — г") ш О по модулям /(г) и р'. Выше был рассмотрен только частный случай для 9(х) = 1. Но обе части этого сравнения можно умножить на полинам Хенселя Ь(х) и получить, что 1 — хл ш О по модулям /(х) и р'.
Замечанье. Более "элементарное" доказательство результата в (с) можно получить без помощи производящих функций, если использовать метод, аналогичный примененному в ответе к упр. 8. Если Аз+„— — А + р'В» для и = г, г + 1, ..., г + Ь вЂ” 1 и некоторых целых чисел В, то такое же соотношение имеет место для всех и > г, если определить В„эл,В»ллгл,...
заданным рекуррентным соотношением. Так как полученная последовательность для В является линейной комбинацией смещений последовательности А„, получим Вл„.„ш В„(по модулю р») для всех достаточно больших значений и. Теперь Л(р'+') должно быть кратным Л = Л(р'). Для всех достаточно больших и справедли- вы соотношения А»(л = А»+р'(В»+ В ех+ В»+эх+. + В.кз-цх) ш 4 +ур'В (по модулю ры) при 1 = 1,2,3,....
Никакие/с последовательных В не кратны р; отсюда немедленно следуют соотношения Л(р'+') = рЛ(р") р Л(ре+э) при е > 2. Необходимо еще доказать, что Л(р"еэ) ф рЛ(р'), когда р нечетно и е = 1. Положим Вхе„= В + рС„ и заметим, что С 41 ш С„(по модулю р), когда и достаточно велико. тогда А„+р эз А„+ рэ (В„+ (Р|)С„) (по модулю рэ), и доказательство окончено. Историю решения этой задачи можно найти в работе Моргана Варда (Могбан Жахе(, Тгзлэ. Ашег. Ма(Ь. Яос.
36 (1933), 600-626); см. также работу Д. В. Робинсона (О. ЛЛ|. ВоЬ(паол, АММ (3 (1966), 619-621). 12. Длина периода по модулю 2 не может быть больше 4. Длина периода по модулю 2'+| не может быть больше удвоенной длины максимального периода шо(! 2'. Это следует из предыдущего упражнения. Поэтому длина максимального возможного периода равна 2 + . »+1 Она достигается, например, в тривиальном случае при а = О, Ь = с = 1. 13, 14. Очевидно, что Я„»1 = л„, поэтому Л' является делителем Л.
Пусть наименьшее общее кратное Л' и Л| равно Л'„а Л' определяется аналогично. Справедливы соотношения Л + У» ш Я ш Х„ем = Х + У„ем, поэтому Л', кратно Ль Аналогично можно показать, что Л~э кратно Л|. Это дает желаемый результат. (Он являетгл»нанлучшим из возможных" в том смысле, что последовательности, для которых Л' = Ле, могут быть построены так же, как последовательности, для которых Л' = Л.) 16. Алгоритм М генерирует (Х еь, У„) на шаге М1 и дает на выходе 8» е» Х„еь е„на шаге МЗ для всех достаточно больших и. Таким образом, (Я„) имеет период длиной Л', где Л' —. наименьшее положительное целое число, такое, что Х»еь-е„= Х +1+1-е „, длЯ всех больших и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
