Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 10
Текст из файла (страница 10)
В данком упражиеиии такие утверждения опровергаются; в сущности, следует удалить два разряда длины слова, чтобы сохранить возможность прибавить с, когда т будет степенью 2.] 10. [МЯ1] Для каких значеиий т справедливо Л(ш) = гг(ш)г ь 11. [Мхв] Пусть х — нечетное целое число, большее, чем 1. (а) Покажите, что существует единственное целое число у > 1, такое, что х щ 2г =" 1 (по модулю 2г+'). (Ь) Дано, что 1 < х < 2' — 1 и что / является соответствующим целым числом и. (а). Покажите, что порядок х по модулю 2' равен 2' г.
(с) В частности, зто доказывает утверждения (1)-(га) теоремы С. 12. [М26] Пусть р — простое нечетное числа. Если е > 1, докажите, что а является первообразиым элементом по модулю р' тогда и только тогда, когда а — первообразиый элемеит по модулю р и аэ ' щ 1 (по модулю рг). (Предположите, что Л(р") = р' '(р — 1), Этот факт доказан в упр. 14 и 1б ниже.) 13.
[Мйй] Пусть р — простое число. Задано, что а не является первоабразиым элементом по модулю р. Покюките, что каждое а кратно р или аш Пг" щ 1 (по модулю р) для некоторых простых чисел в, делящих р — 1. 14. [М18] Предположим, что е > 1, р — печатное простое число и а — первообразиый элемент по малулго р.
Докюките, чта либо а, либо а+ р является перваобразным элементом по модулю р'. [Указание. См, упр. 12.] 15. [МЙз] (а) Пусть аг и аг взаимно просты с гл и пусть их порядки по модулю гл равны соответственно Лг и Лг. Предположим, что Л является наименьшим общим кратным Лг и Лг, Докажите, что а" ,а"„г имеют порядок Л по модулю т для соответствующик целых чисел кг и кг [Указанае. Рассмотрите сиачала случай, когда Л1 и Лг — взаимио простые числа,) (Ь) ПуЬть Л(т) — максимальный порядок любого элемента по модулю т. Докажите, что Л(т) кратно порядку каждого элемента по модулю т, т.
е. что а" ~ "П щ 1 (по модулю т) всегда, когда а и т — взаимно простые числа, (Не используйте теорему В.) ь 16. [МЩ] (Срщесшваванпе перваабразнмх корией.) Пусть р — простое число. а) Рассмотрим полипом у(х) = х" + сгх" ' + .. + с, где с; — целые числа, Дано, что а — целое число, для которого у(а) эз О (по модулю р). Покажите, что существует полипом а(х) = х" +фх" + .. +а„ с целыми коэффициентами, такой, что у(х) гв (х — а)д(х) (по модулю р) для всех целых х, Ь) Пусть /(х) — такой же поливом, как в (а).
Покажите, что у(х) имеет не более и различных "корней" по модулю р, т. е. существует не более п целых чисел а, О < а < р, таких, что у(а) щ О (по модулю р). с) Так же, как и в упр. 15, (Ь), полинам у(х) = хыо~ — 1 имеет р — 1 различных корней; следовательно, существует целое число а с порядком р — 1. 17. (Мйб] Не все значения, перечисленные в теореме П, можно получить, используя построения, приведенные в разделе, например 11 — не первообразный элемент по модулю 5'. Как это возможно, если 11 леллеямл первообразным элементом по модулю 1О' согласно теореме ПУ Какие из чисел, перечисленных в теорема Р, являются одновременно первообразными элементами по малулям 2' и 5'1 18. (М86] Докажите теорему Р (см. предыдущее упражнение), 19.
(46] Составьте таблипу нескольких подходящих множителей а для каждого из значе. ний нц внесенных в табл. 3,2.13-1, предполагая, что с = О. ь 20. (М84] (Дж. Марскчья (О. Магэаб!1а).) Назначение упражнения состоит в изучении длины периода произвольной линейной конгруэнтной последовательности. Пусть 1'о = 1+ а+ + а" ', так что Х„= (АУ„+ Хо) шоб т для некоторой константы А из условия 3.2.1 — (8). а) Докажите, что длина периода (Х„) равна длине периода (1' шабли'), когда т' = ш/Асб(А, га) . Ь) Докажите, что длина периода (1'„шобр') удовлетворяет следующим требованиям, когда р — простое число. (1) Если а шод р = О, длина периода равна 1.
(0) Если а шобр = 1, оиа равна р', за исключением случаев, когда р = 2, е > 2 и а шод 4 = 3. (ш) Если р = 2, е > 2 и а пик14 ж 3, она равна удвоенному порядку а по модулю р' (см. упр. 11), за исключением случая, когда а ж -1 (по ьюдулю 2'), прн котором она равна 2. (Ь ) Если а шод р > 1, длина периода равна порядку а по модулю р'. 21. (М26] Пусть в линейной конгруэнтной последовательности с максимальным периодом Хо = О о — наименьшее положительное целое число, такое, что а' щ 1 (по модулю а1). Докажите, что Асб(Х„ю) = о (Асд — наибольший общий делитель. — Прим. иерее.). ь 22.
(Мйб] Обсудите проблему нахождения модулей т = Ь" ж Ь' ш 1 таким образом, чтобы генераторы, использующие вычитание с заимствованием и суммирование с первнбсам (см. упр. 3.2.1.1-14), имели очень длинные периоды. 3.2.1.3. Потенциал. В предыдущем разделе бьио показано, что максимальный период может быть достигнут, когда Ь = а — 1 кратно каждому простому делителю т, и Ь должно быть также кратно 4, если ш кратно 4. Если г — основание системы счисления машины (з = 2 для бинарного компьютера и л = 10 д„ця десятичного компьютера), ш — длина слова в компьютере г', множитель пыл~+1, 2<А<с, (1) удовлетворяет этим условиям.
По теореме 3.2.1.2Л можно брать с = 1. Рекуррентное соотношение теперь имеет вид Х„1 = ((за+1)х„+1) шобх', (2) и зта уравнение означает, что можно избежать умножения; просто достаточно перемещения и суммирования, Например, пусть а = Вз+ 1, где  — размер байта компьютера й1Х. Программа (3) ЬОА Х: 31А 2,' АОР Х; 1ИСА 1 Ь' вт О (по модулю т), (Целое число э всегда существует, когда множитель удовлетворяет условиям теоремы 3.2.1.2А, так как Ь кратно каждому простому делителю т.) Можно анализировать случайность последовательности, положив Ле = О, так как О встречается в периоде.
При этом предположении соотношение 3.2.1-(б) сво. днтся к Х„= ((а" — 1)с/Ь) шоб т: н, если разложить выпажение а" — 1 = (Ь+ 1)" — 1 по биномиальной формуле, получится Х„= с(п+ ( ) Ь+" + ~ ) Ь' ') шод т. Все члены разложения Ь', Ь'+' и т.
д, можно исключить, так как они кратны т. Уравнение (5) сталь поучительно, чта необходимо рассмотреть нскоторыс специальные случаи, Если а = 1, потенциал равен 1 н Х„ж сп (по модулю т), как мы уже видели, так что последовательность наверняка не случайна. Если потенциал равен 2, то Х„ы сп, + сЬ("), и снова последовательность не совсем случайна. Действительно, в этом случае Хп„ы — Х„ь с+ сЬп. Таким образом, разность между последовательно генерируемыми числами выраже- на простой зависимостью от и. Точка (Х„, Хв~м Х„+в) всегда лежит на одной из четырех плоскостей в трехмерном пространстве: х — 2у+х =И вЂ” т, х — 2у + в = Н вЂ” 2т, х — 2у+г = и+ т, х — 2у+х=й, где о = сЬ шос( т.
Если потенциал равен 3, то последовательность становится более или менее похожей на случайную, но все еще существует высокая степень зависимости между Х„, Хв+~ и Х„.~т. Тесты показывают, что последовательности с потенциалом 3 по- прежнему недостаточно хороши. Сообщалось, что приемлемые результаты были получены в некоторых случаях при потенциале, равном 4, но зта оспаривалось может использоваться вместо программы, приведенной в разделе 3.2.1,1, и время выполнения программы уменьшается от 16и до уи.
По этой причине множители, имекшие вид (1), широко обсуждались в литературе. Онн действительно рекомендованы многими авторами. Однако пепвые несколько лет экспериментирования с этим методом убедительно показали, что множителей, лмеюгдпх простой ннд (1), следует избегать, Сгенерированные числа просто недостаточно случайны. Ниже в этой главе будет рассмотрена одна довольно сложная теория, связанная с недостатками всех известных плохих линейных конгруэнтных генераторов случайных чисел.
Однако некоторые генераторы (такие, как (2)) настолько ужасны, что достаточно сравнительно простой теории, чтобы исключить их из рассмотрения. Эта простая теория связана с понятием "потенциал", которое мы сейчас обсудим. Потенциал линейной конгрузнтной последовательности с максимальным периодом определяется как наименьшее целое число в, такое, что другими исследователями.
Кажется, что последовательности с потенциалом б и выше обладают достаточно хорошими случайными свойствами. Предположим, например, что пз = 2зз и а = 2з + 1. Тогда Ь = 2", так что величины Ьз = 2зь кратны пз, когда Ь > 18: потенциал равен 2. Если /е = 17, 16,...,12, то потенциал равен 3 и значение потенциала 4 достигается для Ь = 11, 10,9. Таким образом, с точки зрения потенциала множители приемлемы при й < 8. Это означает, что а < 257, но, как мы увидим позже, малых множителей также следует избегать. Итак, все множители вида 2" + 1, когда т = 2зз, исключены. Когда т равно ш ш 1, где ю — длина слова компьютера, пз, вообще говоря, не делится на высокие степени простых чисел и высокий потенциал невозможен (см.
упр. 6). Таким образом, в этом случае не следует использовать метод максимального периода; лучше использовать метод чистого умножения со значением с = О, Нужно подчеркнуть, что высокий потенциал является необходимым, но недостаточным условием случайности; мы использовали понятие потенциала для того, чтобы исключить несостоятельные генераторы, но не д.ия того, чтобы безусловно принимать все генераторы с высоким потенциалом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
