b) Пусть f{x) - такой же полином, как в (а). Покажите, что /(х) имеет не более п различных "корней" по модулю р, т. е. существует не более п целых чисел а, О < а < р, таких, что /(о) = О (по модулю р).

c) Так же, как и в упр. 15, (Ъ), полином /(х) = х*"" - 1 имеет р - 1 различных корней; следовательно, существует целое число о с порядком р - 1.

17. Не все значения, перечисленные в теореме D, можно получить, используя построения, приведенные в разделе, например 11 - не первообргизный элемент по модулю 5. Как это возможно, если 11 является первообразным элементом по модулю 10= согласно теореме D? Какие из чисел, перечисленных в теореме D, являются одновременно первообразными элементами по модулям 2 и 5?

18. [М25] Докажите теорему D (см. предыдущее упражнение).

19. [40] Составьте таблицу нескольких подходящих множителей а для каждого из значений ш, внесенных в табл. 3.2.1.1-1, предполагая, что с = 0.

► 20. [MS4] (Дж. Марсалья (G. Marsaglia).) Назначение упражнения состоит в изучении длины периода произвольной линейной конгруэнтной последовательности. Пусть У„ = 1 -t- о -t- 4- а"~, так что Хп = {AYn + Хо) mod m для некоторой константы А из условия 3.2.1-(8).

a) Докажите, что длина периода (Хп) равна дайне периода (Vmodm), когда т = m/gcd(,m).

b) Докажите, что длина периода (Уп mod р) удовлетворяет следующим требованиям, когда р - простое число, (i) Если amodp = О, длина периода равна 1. (ii) Если о modp = 1, она равна р, за исключением случаев, когда р = 2, е>2ио mod 4 = 3. (iii) Если р = 2, е>2ио mod 4 = 3, она равна удвоенному порядку о по мод>лю р (см. упр. 11), за исключением случая, когда о = -1 (по модулю 2), при котором она равна 2. (iv) Если о mod р > 1, длина периода равна порядку о по модулю р.

21. [М25] Пусть в линейной конгруэнтной последовательности с максимальным периодом Хо = О S - наименьшее положительное целое число, такое, что о* = 1 (по модулю т). Докажите, что gcd{Xs,m) = s (gcd - наибольший общий делитель. - Прим. перев.).

► 22. [М25] Обсудите проблему нахождения модулей m = 6* ± б ± 1 Таким образом, чтобы генераторы, использующие вычитание с заимствованием и суммирование С переносом (см. упр. 3.2.1.1-14), имели очень длинные периоды.

3.2.1.3. Потенциал. В предыдущем разделе было показано, что максимальный период может быть достигнут, когда b = а - 1 кратно каждому простому делителю тп, а b должно быть также кратно 4, если тп кратно 4. Если z - основание системы счисления машины (z - 2 для бинарного компьютера и 2 10 для десятичного компьютера), т - длина слова в компьютере 2*, множитель

а = -Н 1, 2 < А; < е, (1)

удовлетворяет этим условиям. По теореме 3.2.1.2А можно брать с = 1. Рекуррентное соотношение теперь имеет вид

Хп+1 = {{z + l)Xn + l) mod Z, (2)

и это уравнение означает, что можно избежать умножения; просто достаточно перемещения и суммирования.

Например, пусть а = -И, где В - размер байта компьютера MIX. Программа

LDA X; SLA 2; ADD X; INCA 1 (3)

может использоваться вместо программы, приведенной в разделе 3.2.1.1, и время выполнения программы уменьшается от 1би до 7и.

По этой причине множители, имеющие вид (1), широко обсуждались в литературе. Они действительно рекомендованы многими авторами. Однако пеп-вые несколько лет чкспериментирования с этим методом убедительно показали, что множителей, имеющих простой вид (1), следует избегать. Сгенерированные числа просто недостаточно случайны.

Ниже в этой главе будет рассмотрена одна довольно сложная теория, связанная с недостатками всех известных плохих линейных конгруэнтных генераторов случайных чисел. Однако некоторые генераторы (такие, как (2)) настолько ужасны, что достаточно сравнительно простой теории, чтобы исключить их из рассмотрения. Эта простая теория связана с понятием "потенциал", которое мы сейчас обсудим.

Потенциал линейной конгруэнтной последовательности с максимальным периодом определяется как наименьшее целое число s, такое, что

Ь* = О (по модулю т). (4)

(Целое число s всегда существует, когда множитель удовлетворяет условиям теоремы 3.2.1.2А, так как b кратно каждому простому делителю т.)

Можно анализировать случайность последовательности, положив Ло = О, так как О встречается в периоде. При этом предположении соотношение 3.2.1-(6) сводится к

Хп = ((а" - 1)с/Ь) modm;

и, если разложить выражение а" - 1 = (Ь + 1)" - 1 по биномиальной формуле, получится

Л„ = с (п + ) + • • + (") "0 """

Все члены разложения Ь*, Ь*"" и т. д. можно исключить, так как они кратны т.

Уравнение (5) столь поучительно, что необходимо рассмотреть некоторые специальные случаи. Если а = 1, потенциал равен 1 и Х„ = сп (по модулю т), как мы уже видели, так что последовательность наверняка не случайна. Если потенциал равен 2, то Хп = сп 4-06(2), и снова последовательность не совсем случайна. Действительно, в этом случае

Х„+1 - Хп=с+ сЬп.

Таким образом, разность между последовательно генерируемыми числами выражена простой зависимостью от п. Точка (Л„,Л,г+1,Л„+2) всегда лежит на одной из четадрех плоскостей в трехмерном пространстве:

x - 2y + z = d-rm, X - 2y + z = d - тп,

x-2y + z = d, x-2y + z = d- 2т,

где d = cb mod т.

Если потенциал равен 3, то последовательность становится более или менее похожей на случайную, но все еще существует высокая степень зависимости между Хп, Хп+1 и Хп+2- Тесты показывают, что последовательности с потенциалом 3 по-прежнему недостаточно хороши. Сообщалось, что приемлемые результаты были получены в некоторых случаях при потенциале, равном 4, но это оспаривалось

другими исследователями. Кажется, что последовательности с потенциалом 5 и выше обладают достаточно хорошими случайными свойствами.

Предположим, например, что m = 2 и а = 2* + 1. Тогда b = 2*, так что величины = 2* кратны т, когда к > 18: потенциал равен 2. Если к = 17,16,..., 12, то потенциал равен 3 и значение потенциала 4 достигается для к = И, 10,9. Таким образом, с точки зрения потенциала множители приемлемы при А; < 8. Это означает, что а < 257, но, как мы увидим позже, малых множителей также следует избегать. Итак, все множители вида 2* -Ь 1, когда m = 2, исключены.

Когда т равно w ±1, где w - длина слова компьютера, тп, вообще говоря, не делится на высокие степени простых чисел и высокий потенциал невозможен (см. упр. 6). Таким образом, в этом случае не следует использовать метод максимального периода; лучше использовать метод чистого умножения со значением с = 0.

Нужно подчеркнуть, что высокий потенциал является необходимым, но недостаточным условием случайности; мы использовали понятие потенциала для того, чтобы исключить несостоятельные генераторы, но не для того, чтобы безусловно принимать все генераторы с высоким потенциалом. Линейные конгруэнтные последовательности должны пройти "спектральный тест", обсуждаемый в разделе 3.3.4, прежде чем они будут признаны случайными.

УПРАЖНЕНИЯ

1. [МЮ] Покажите, что независимо от размера байта В компьютера MIX программа (3) генерирует последовательность случайных чисел с максимальным периодом.

2. [10] Чему равен потенциал генератора, предложенного в программе (3) для компьютера MIX?

3. [11] Чему равен потенциал линейной конгруэнтной последовательности, когда m = 2 и о = 3141592621? Чему равен потенциал, если множитель равен а = 2 -t- 2 -t- 2 -f-1?

4. [15] Покажите, что если ш = 2* > 8, то максимум потенциала достигается прИ а mod 8 = 5.

5. [М20] Дано, что т = р... р* и а - 1 + кр{ ?(< где а удовлетворяет условиям теоремы 3.2.1.2А и ки тп - взаимно простые числа. Покажите, что потенциал равен тах(Ге1 Л,...,Ге,/Л1).

► 6. [20] Какие значения m = w±l из табл. 3.2.1.1-1 могут быть использованы в линейной конгруэнтной последовательности с максимальным периодом, чтобы ее потенциал был равен 4 или выше? (Воспользуйтесь результатом упр. 5.)

7. [М20] Когда о удовлетворяет условиям теоремы 3.2.1.2А, оно взаимно просто с т; поэтому существует число о, такое, что аа = 1 (по модулю тп). Покажите, что о может быть просто записано в терминах 6.

► 8. [MS6] Генератор случайных чисел, определенный как Хп+\ = (2 + 3)Х„ mod 2 и Хо - 1, был протестирован следующим образом: пусть У„ = [10Jtn/2°J; тогда У„ должен быть случайной цифрой между О и 9 и тройка цифр (Узп, Узп-ц, Узп+г) должна принимать каждое из 1 ООО возможных значений от (О, О, 0) до (9, 9, 9) с приблизительно равными частотами. Но после того как было проверено 30 ООО значений, оказалось, что одни тройки встречались крайне редко, а другие - чаще, чем должны были бы. Можно ли объяснить такой неудачный результат испытаний?