AOP_Tom2 (1021737), страница 32
Текст из файла (страница 32)
По этой причине множители, имеющие вид (1), широко обсуждались в литературе. Онн действительно рекомендованы многими авторами. Однако пепвые несколько лет экспериментирования с этим методом убедительно показали, что множителей, имеющих простой влд (1), гтедует избегать. Сгенерированные числа просто недостаточно случайны. Ниже в этой главе будет рассмотрена одна довольно сложная теория, связанная с недостатками всех известных плохих линейных конгруэнтных генераторов случайных чисел. Однако некоторые генераторы (такие, как (2)) настолько ужасны, что достаточно сравнительно простой теории, чтобы исключить их из рассмотрения. Эта простая теория связана с понятием "потенциал", которое мы сейчас обсудим.
Потенциал линейной конгруэнтной последовательности с максимальным периодом определяется как наименьшее целое число э, такое, что другими исследователями. Кажется, что последовательности с потенциалом 5 и выше обладают достаточно хорошими случайными свойствами, Предположим, например, что т = 2зз и а = 2ь + 1. Тогда 5 = 2", так что величины Ьз = 2зь кратны пз, когда )с ) 18: потенциал равен 2. Если )з = 17, 16,...,12, то потенциал равен 3 и значение потенциала 4 достигается для )с = 11, 10, 9.
Таким образом, с точки зрения потенциала множители приемлемы при /г < 8. Это означает, что а < 257, но, как мы увидим позже, маззмх множителей также следует избегать. Итак, все множители вида 2ь + 1, когда пз = 2зз, исключены. Когда т равно ш ш 1, где ю — длина слова компьютера, т, вообще говоря, не делится на высокие степени простых чисел н высокий потенциал невозможен (см.
упр. 6). Таким образом, в этом случае не следует использовать метод максимального периода; лучше использоиать метод чистого умножения со значением с = О. Нужно подче5зкнуть, что высокий потенциал является необходимым, но недостаточным условием случайности; мы использовали понятие потенциала для того, чтобы исключить несостоятельные генераторы, но не дэя того, чтобы безусловна принимать все генераторы с яысоким потенциалом. Линейные конгрузнтные последовательности должны пройти "спектральный тест", обсуждаемый в разделе 3.3.4, прежде чем они будут признаны случайными.
УПРАЖНЕНИЯ 1. [МХО] Покажите, что независимо от размера байта В компьютера Н1Х программа (3) генерирует последовательность случайных чисел с максимальным периодом. 2. [1О] Чему равен потенциал генератора, предложенного в программе (3) для компьюера НХХ? 3. [11] Чему равен потенциал линейной конгруэнтной последовательности, когда зп = 2зз и а = 3141592521? Чему равен потенциал, если множитель равен а = 2зз+ 2'з+ 2" + 1? 4. [15] Покажите, что если т = 2' > 8, то максимум потенциала деетнтаятся Прй 0 П!00 8 = 5.
5. [МВО] Дано, что пз = р" ,.. р" ,и а = 1+?зр['... р1', где а удовлетворяет условиям теоремы 3.2.1.2А н 1с'н т — взаимно простые числа. Покажите, что потенциал равен зпах([ез//з],..., [ез//з]). О. [20] Какие значения т = ш*1 из табл. 3.2.1.1-1 могут быть использованы в линейной конгруэнтной последовательности с максимальным периодом, чтобы ее потенциал был равен 4 илн выше? (Носпользуйтесь результатом упр. 5.) 7. [М20] Когда а удовлетворяет условиям теоремы 3.2.1.2А, оно взаимно просто с яи поэтому существует число а', такое, что аа' = 1 (по модулю ш).
Покажите, что а может быть престо записано в терминах 5. 8. [М25] Генератор случайных чисел, определенный как Хз ы = (2 + 3)Хз шод 2 и м зз Хз = 1, был протестиревая следующим образом. пусть 1'„= [10Х„/2'з]; тогда 1'з должен быть случайной цифрой между 0 н 9 н тройка цифр (1"з„, 1'ззэз, 1'з эз) должна принимать каждое нэ 1 000 возможных значений от (О, О. О) Ло (9, 9, 9) с приблизительно равными частотами. Но песне того как было проверено 30 000 значений, оказалось, что одни тройки встречались крайне редко, а другие -- чаще, чем должны были бы. Можно лн объяснить такой неудачный результат испытаний? 3.2.2. Другие методы Конечно, линейные конгруэнтные последовательности — это не единственный источник случайных чисел, который предлагается для использования на компьютере.
В этом разделе будет приведен обзор наиболее существенных альтернативных методов. Одни нз них действительно важны, тогда как другие интересны главным образом потому, что они не так хороши, как хотелось бы. В связи с получением случайных чисел возникает такая общепринятая ошибочная идея — достаточно взять хоро|пий генератор случайных чисел и немного его модифицировать для того, чтобы получить "еще более случайную" последовательность. Часто это не так. Например, известно, что формула Хны = (аХа+ с) пюдт позволяет получить более или менее хорошие случайные числа.
Может ли последо- вательность, полученная из Хь~ ~ — — ((аК„) пюд (гп + 1) + с) шод пт, (2) быть еще более случайной? Ответ: новая последовательность является менее случайной с большой долей вероятности. Таким образом, идея потерпела неудачу и при отсутствии какай-нибудь теории о поведении последовательности (2) мы попадаем в область генераторов типа Х„~1 = 1(Х„) с выбранной наудачу функцией (.
В упр. 3.1-11, 3.1-15 показано, что эти последовательности, вероятно, ведут себя намного хуже, чем последовательности, полученные при использовании более регулярных функций (1). Давайте рассмотрим другой подход к попытке получить подлинно улучшенный вариант последовательности (1). Динейный конгруэнтный метод может быть обобщен, скажем, в квадратичный конгруэнтный метод: Х„+1 = (НХ~ + аХ„+ с) шобгп. (3) В упр.
3 обобщена теорема 3.2.1.2А, чтобы получить необходимые и достаточные условия для а, с и Н, такие, чтобы последовательность, определенная соотношением (3), имела период максимальной длины т. В этом случае ограничения не более жесткие, чем в линейном методе. Для гп, которое является степенью 2, интересный квадратичный метод предложил Р. Р. Ковэю (В.. В. Сохеуоп). Пусть Хешоб4= 2, Х„э1 —— Х„(Х„+1) пюб2', и > О. (4) Данная последовательность может быть вычислена приблизительно с той же эффективностью, что и (1), без любых беспокойств по поводу переполнения.
Этот метод имеет интересную связь с подлинным методом средин квадратов фон Неймана (гоп Кешпапп). Если положить У„' равным 2'Х„, так что 1'„является числом двойной точности, полученным в результате размещения справа е нулей у двоичного представления числа Х„, то У„+~ точно совпадет со средними 2е цифрами У~+2'У„'! Другими словами, метод Ковэю в некоторой степени почти идентичен вырожденному методу средин квадратов двойной точности, однако он гарантирует получение длинного периода. Дополнительное свидетельство его случайности приведено в статье Ковэю, цитируемой в ответе к упр. 8. Другие обобщения выражения (1) также очевидны. Например, можно попытаться увеличить длину периода последовательности.
Период линейной коигруэнтной последовательности довольно длинный; когда т приблизительно равно длине слова компьютера, обычно получаются периоды порядка 10э или больше и в типичных вычислениях используется лишь маленькая часть последовательности. С другой стороны, при рассмотрении идеи "точности" в разделе 3.3.4 получается, что длина периода влияет на степень случайности последовательности. Значит, желательно получить длинный период и существует несколько подходящих для этого методов. Один из них состоит в том, чтобы сделать Ли ы зависящим от Л'„и Х„ы а не только от Х„.
Тогда длина периода сможет достичь значения гп', так как последовательность не станет повторяться, пока ие будет получено равенство (Х„.ьы Х,+х ы) = (Х„Х,ег), Джон Мочли (аппп МапсЫу) в неопубликованной работе, представленной на статистической конференции в 1949 году, расширил метод средин квадратов с помощью рекуррентного соотношения Х„= середнна (Л„1 Хь — в) Простейшая последовательность, в которой Хны зависит более чем от одного из предыдущих значений, — это последовательность чисел Фибоначчи (5) Х„<.1 — — (Л„+ Х„1) шод т. Данный генератор рассматривался в начале 50-х годов, и обычно он дает длину периода, ббльшую, чем тп.
Но тесты показывают, что числа, получаемые с помощью рекуррентного соотношения Фибоначчи, безусловно, недостпаточно случайны, и, таким образом, выражение (5) нас, главным образом, интересует, как элегантный "плохой пример" источника случайных чисел. Можно также рассматривать генераторы вида Хв ы — (Л + Х ь) шос1 гп (6) когда й — сравнительно большое число. Это рекуррентное соо7иошение было введено Грином, Смитом и Клем (Огееп, Бпп!!И апс! К!еш (3АСМ 6 (1959), 527 — 537)), сообщившими, что, когда Й < 15, тестирование последовательнОСтй С ИСПОИЬ30ийнийц критерия "интервалов", описанного в разделе 3.3.2, дала отрицательный результат, хотя при й = 16 результат был положительным.
Намного лучший адаптивный генератор был изобретен Дж, Ж. Митчелом (О. Я. М!!с!зе!!) и Д. Ф. Муром (В. Р. Мооге) в 1958 году [не опубликовано]. Они предложили несколько необычную последовательность, определенную так: Хп (Хл — 24 + Х зз) шос) гп, и > 55, (7) где т четное число, а Хс,...,Хы — произвольные целые не все четные числа. Числа 24 и 55 в данном определении не были выбраны наудачу; эти специальные числа выбраны, оказывается, для того, чтобы определить такую последовательность, младшие значащие двоичные разряды (Х„пюс) 2) которой имеют длину периода 2ы — 1. Очевидно, последовательность (Х„) должна иметь период по крайней мере такой же длины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
