AOP_Tom2 (1021737), страница 167
Текст из файла (страница 167)
5. Потенциал равен наименьшему из значений е, таких, что уз в > с| для всех 71 6. Модуль должен делиться на 2' нли на ре (для нечетных простых р) для того, чтобы потенциал был ранен 4. Такими будут только величины т = 2|| + 1 н 10в — 1. 7. а' = (1 — 5+ Ь вЂ” - ) шоб т, где члены Ь', Ь'е' и т.
д. опускаются (если е — потенциал). г 8. Так как Х всегда нечетно, Хеег = (2 + 3 2 + 9)Х„шо62 '" = (2 +6Хае| — 9Х„) шод2 Если даны Уа и У„ем то нозиожности для У„ег (5+ 6(У„е., + е,) — 9(У„+ ег)) шод 10, 0 < е| < 1 и О < ег < 1, ограничены и неслучайны. Замечанье. Если множители, предложенные в упр. 3, были бы, скажем, равны 2 + 2'в + 2 + 1, а не 2|з + 2|з + 2 + 1, иожно было бы аналогично показать, что зз |в Хаег — 10Х е|+25Х„ш сопвеапе (по модулю 2|').
Вообще говоря, а хб не должно делиться на высокие степени 2, когда б мвлб. В противном случае получится "несостоятельность второго порядка". Более подробно этот вопрос обсуждается а разделе 3.3.4. Генератор из этого упражнения рассматривался в работе Мак-Ларена и Марсвлья (МасБагеп, Магваб!|а, 3АСМ 13 (1965), 83-89). Недостатки таких генераторов, впервые были продемонстрированы М.
Гринбергером (М. Сгеепбег8ег), САСМ 8 (1965), 177-179). Даже через десять лет после появлении этой работы подобные генераторы широко использовались (см. обсуждение 85900 а разделе 3.3.4). РАЗДЕЛ 3.2.2 1. Метод следует применять с большой осторожностью. Прежде всего, аП, вероятно, будет настолько большим, что добавлять с/т не имеет смысла, н операции по "то|1 П почти уничтожат любые следы оставшихся от добавления значений.
Мы заключаем, что необходимо испольэовать арифметические операции с плавающей запятой с двойной точностью. Даже с двойной точностью нужна уверенность, что нет округления и т. д, иначе последовательность чисел будет вести себя совершенно по-другому, так как нарушатсн теоретические основы хорошего поведения последовательности (но см упр. 23).
2. Х„+1 равно либо Хч 1 + Лв, либо Хя 1 + Хя — гп. Если Х„+1 < Хв, то должно быть Х„+~ = Х -1 + Х вЂ” т; отсюда Х ьг < Х„ 3. (а) Подчеркнутые числа — это Щ после шага МЗ. Таким образом, потенциал может быть сведен к 1! (См. комментарии, приведенные в ответе к упр. 15.) (Ь) Подчеркнутые числа — это г'[2[ после шага В2 становится такой: 10.. 00 00...00 СОМТЕМТЯ(А) Последовательность значений Х 10...00 СОМТЕМТБ(А) 8. Можно предположить, что Хо = 0 и ш = р', как и при доказательстве теоремы 3.2 1.2Л. Сначала предположим, что последовательность имеет длину периода р' Отсюда следует, что период попчедовательиости по модулю р~ имеет длину ру для 1 < / < с, В этом случае выход значительно лучше входа; он привносит повторяющийся цикл длиной 40 погле 46 шагов; 236570 05314 72632 40110 37564 76025 12541 73625 03746 (30175 24061 52317 46203 74531 60425 16753 02647).
Можно легко найти цикл, применяя мелоды из упр 3 1 — 7 к приведенной выше таблице до повторяющихся столбцов. 4. Байты младшего порядка многих случайных последовательностей (например, линейная конгрузнтная последовательность с ш = длина слова) намного менее случайны, чем байты высокого порядка (см. раздел 3.2.1.1). 5. Эффект рандомизации будет сведен к минимуму, потому что )г[/] всегда будет содержать числа из определенного интервала, а именно -- 3/А < Ц/)/гл < () + 1)/Е Однако использование подобных подходов вполне допустимо.
Можно положить У„= Х„.1 или выбРать 7 из Лчи извлекаЯ некотоРые цифРы из сеРедины числа, а не из его левой части. Никакое из этих предложений не будет удлинять период, как это делает алгоритм В. (В упр. 27 показано, однако,что алгоритм В необязательно увеличивает длину периода.) 6. Например, если Х /т, < -', то Х ь1 — — 2Х Т. (Мантель В.
[11'. 54шие!, №еои Агс)беГкоог ЧЪАиги)е (2) 1 (1897), 172 — 184.[ ОО ..01 00...01 00...10 00...10 иначе некоторые вычеты по модулю р! никогда не будут встречаться. Ясно, что с не кратно р: с другой стороны, Л должно быть кратно р. Если р < 3, то легко доказать необходимость условий (ш) и (!т) методом проб и ошибок, поэтому можно предположить, что р > 5.
Если !4 д О (по модулю р), то дх~+ аг+ с = !((к+ а!) + с! (по модулю р') для некоторых целых а! и с! и для всех целых х, Эта квадратичная форма принимает одни и те же значения в точках х и -х — 2а!, поэтому она не может принимать все значения по модулю р'. Следователыю, !): — 0 (по модулю р) и, если а (е 1, выполнялось бы равенство !(г + ах + с = х (по модулю р) для некоторых т, а это противоречит тому факту, что последовательность по !вой р имеет период длиной р. Чтобы показать достаточность условий, можно воспользоваться теоремой 3.2.1.2А и рассл!с!треть несколько тривиальных случаев, когда т = р', где е > 2. Если р = 2, то ясно, что Х„т ш Х -!- 2 (по модулю 4), если р = 3, получим Хяез ш Մ— И+ 3с (по мочу!по 9), используя (!) и (й). Для р > 5 можно следующим образом доказать, что Л „= Х -~- рс (по модулю р!).
Пусть 4 = рг, о = 1 + рз. Тогда, если Л = сп + рУ„ (по модулю р ), необходимо получить 1'„. ! = и с г + псэ + У„(по модулю р); поэтому 3 2 з )э = (") 2сзг + (з) (с'г т сз) (оо модулю р). Таким образом, 1 р шоб р = О, и соотношение доказано. Сейчас можно доказать, что последовательность (Х„) целых чисел, определенная в "указании", удовлетворяет соотношению Л'„~р! = Л„+ 1р~ (по модулю р е'), п>0, для некоторых 1 с !глоб р ф О и для всех 1 > 1.
Этого достаточно для доказательства, что последовательность (Х„шоб р") имеет период длиной р', если длина периода является делителем р', ио не делителем р' '. Соотношение, приведенное выше, уже было установлено для 1 = 1, и для / > 1 оно может быть получено по индукции следующим образом. Пусть Х„.„, = Х4 -р !р'+ г„р' ' ( моду рте'); тогда из квадратичного закона для генерирования последовательности с !( = рг, а = 1 + рз следует, что У„е! = 2ггпс+ зг + У„(по модуля! р). поэтому Я„+р ш л,. (по модулю р).
Следовательно, Х„ть ! = Х4 91(ерш+Я„р~ ) (по модулю р~+~) для й = 1, 2, 3, .... Если положить теперь )с = р, то на этом доказательство будет завершено. Замечание. Если 1(х) — — полипом степени, более высокой, чем 2, и Х е! —— ДХь)! анализ будет несколько сложнее, хотя можно использовать тот факт, что 1'(т + р ) = У(ш) + р )г(п!) + рз'! "(тп))2!+, для доказательства того. что многие полиномиальные последовательности дают максимальный период. Например, Ковэю (Сочеуоп) доказал, что период равен ш = 2', если 1(0) нечетио, ~'(2) = 1, 1'"(1) = 0 и 1(2 + 1) = Щ) + 1 (по модулю 4) для у = 0,1.2,3.
[бйп!(!еэ !и Арр1!ес( Магб. 3 (Р1!!1а!)е!рЬ1а: 31ЛМ, 1969), уо-ш.) 9. Пусть Х = 41~, -!-'2; то!да последовательность У удовлетворяет квадратичному рекуррентному соотношению 1;э ! = (4У;,~ + ЬУ; + 1) !поб 2' 10. Случай П Хе = О, Х! —— 1; следовательно, Л' = Р„. И!цем наименьшее и, для которого г' — ш О и Х'„т! = 1 (по модулю 2'). Так как Гз = Р,(Г„! + Г„з.!), Рз ш = ге + гьз.!, з з ют! найдем ивдукцией по с, что для е > 1 Гз м ! = 0 и Рз,з.
!„., ги 2' + 1 (па модулю 2'+ ). Это означает,что период является делителем 3 2' ',но не 3 2" з. Следовательно, период равен либо 3. 2' ', либо 2' '. Но Гм-~ — всегда нечетное число (так как только гз»вЂ” четное). Случай дл Хе —— а, Х1 = Ь. Тогда Х ш аг» ~ + Ьг». Нужно найти наименьшее положительное и, такое, что а(Р' .р1 — Г„) + Ьг» = а и аг"„+ Ьг»+1 ш Ь. Это влечет, что (Ь вЂ” аЬ вЂ” а )г» ш О, (Ье — аЬ вЂ” а~)(г».р1 — 1) = О. И Ь~ — аЬ вЂ” а нечетко (т. е. оно простое относительно т). Итак, условие эквивалентно тому, что Р'„ш О, Р»е1 ш 1, Метод определения периода Н для любого модуля впервые был приведен в статье Д. Д.
Волла (Р. Р. '1тай, АММ 67 (1960], 525 — 532). Другие факты относительно последовательности Фибоначчи по модулю 2' найдены Б. Иенссеном (В. 3апшоп, Вандою НпшЬег Сепегарогв (Бгос1сЬо!ш: А!пир ни 5с уу1Ьэей, 1966), Яесбоп 3С1). 11. (а) .Легко видеть, что х" = 1+/(х)и(х)+р'и(х) для некоторых и(х) и е(х), где е(х) ф 0 (по модулю /)(х) и р.
По биномиальной теореме хР 1+ +1„() э+1 плюс следующие члены, конгруэнтные нулю по модулям /(х) и р'+з. Так как р' > 2, то х"р гя 1 + р'+'о(х) по модулям /(х) и р'и . Если р'+'и(х) ш 0 по модулям /(х) и р'+~, должны сущестновать полиномы а(х) и Ь(х), такие, что р'+'(о(х) + ра(х)) = /(х)Ь(х).
Поскольку /(О) = 1, получаем, что Ь(х) кратно р'+' (по лемме Гаусса 4.6.1С). Отсюда е(х) ш 0 по модулям /(х) и р. В итоге получено противоречие. (Ь) Если х~ — 1 = /(х)и(х) + р'е(х), то С( ) = и( )/(х" — 1) + р'о(х)//( П ' — 1); следовательно, А»+х ш А (по модулю р') для базьших и. Обратна, если (А„) обладает последним свойством, то С(х) = и(х)+о(х)/(1-х )+р'Н(х) для некоторых полиномов и(х) и и(х) и некоторого степенного ряда Н(х), таких, что ряд и полиномы имеют целые коэффициенты. Отсюда следует равенство ) — х" = и(х)/(х)(1 — х")+о(х)/(х)+р'Н(х)/(х)(1 — х~), и Н(х)/(х)(1 — х~) является полина»гон, так как другой член равенства — поленом.
(с) Достаточно доказать, что неравенство Л(р') ф Л(р'э ) влечет такие соотношения Л(р'~~) = рЛ(р') р Л(р'ьз). Из (а) и (Ь) следует, что Л(р'+з) ф рЛ(р') и что Л(рр ы) является делителем рЛ(р'), но не Л(р'). Следовательно, если Л(р') = руд, где д шод р ~ О, то Л(р*+') должно равняться руР'6, где 6 — делитель д. Но сейчас Х„+рг м ш Х» (по модулю р'); значит, ргР'6 кратно руд и 6 = д. [Замечание. Предположение о том, что р' > 2, необходимо; например, если а1 = 4, аз = -1, Ь = 2, то (А„) = 1, 4, 15, 56, 209, 780, ...; Л(2) = 2, Л(4) = 4, Л(8) = 4.) (6) д(х) =Хо+(Х1 — а1Хе)х+ +(Хь-1 — а1Хь з — аэХ» з — — ар 1Хо)хь (е) Утверждение (Ь) можно обобщить для С(х) = д(х)//(х); следовательно, предположение, что длина периода ранна Л, влечет то, что д(х)(1 — х~) ш 0 по модулям /(г) и р'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
