Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 11
Текст из файла (страница 11)
Чинейиые конгруэнтные последовательности должны пройти 'спектральный тест", обсуждаемый в разделе 3.3.4, прежде чем они будут признаны случайными. УПРАЖНЕНИЯ 1. )М10) Покажите, что везависимо ог размера байта В компьютера ИХХ программа (3) генерирует последовательность случайных чисел с максимальным периодом. 2. (10) Чему равен потенциал генератора, предложенного в программе (3) для компьютера ЯХХ? 3.
(11) Чему равен потенциал линейной конгруэнтной последовательности, когда гл = 2зз и а = 3141592621? Чему равен потенциал, если множитель равен а = 2зз + 2'з + 2 + 1? 4. (15) Покажите, что если пз = 2' > 8, то максимум потенциала достигаетгя прй 0 П!06 8 = 5. 5. (М20) Дана, что вз = р",'...р" ,и а = 1+ /ер~'... р1', где а удовлетворяет условиям теоремы 3.2.1.2А и /е и вз — взаимно простые числа.
Покажите, что потенциал равен т ((ез/Ы,...,(е //з)). ° 6. (20) Какие значения гл ж ш ш1 из табл. 3.2.1.1-1 могут быть использованы в линейной конгруэнтной последовательности с максимальным периодом, чтобы ее потенциал был равен 4 или выше? (Воспользуйтесь резучьтатам упр. 5.) ?. (МЗд] 'Когда а удовлетворяет условиям теоремы 3.2.1.2А, оио взаимно просто с пз; поэтому существует число а, такое, что аа ге 1 (по модулю пз).
Покажите, что «~ может быть просто записано в терминах Ь. 8. (М96) Генератор случайных чисел, определенный как Л зз = (2'"+3)Х~ щод2 и Хо = 1, был протестировал следующим образом: пусть У„= )10Л„/2~~1; тогда У„далжеи быть случайной цифрой между 0 н 9 н тройка цифр (Уз», Уз~.зм Уз ч.з) доззкпа принимать каждое из 1 000 возможных значений ат (О, О, О) ло (9, 9, 9) с приблизительно равными частотами. Но после того как было проверено 30 ООО значений, оказалось, что одни тройки встречзлиеь крайне редко„а другие — чаще, чем должны были бы. Можно ли объяснить такай неудачный результат испытаний? 3,2.2, Другие методы Конечно, линейные конгрузнтные последовательности — это не единственный источник случайных чисел, который предлагается для использования на компьютере.
В этом разделе будет приведен обзор наиболее сушественных альтернативных методов. Одни нз них действительно важны, тогда как другие интересны главным образом потому, что они не так хороши, как хотелось бы. В связи с получением случайных чисел возникает такая обшепринятая ошибочная идея — достаточно взять хороший генератор случайных чисел н немного его модифицировать для того, чтобы получить "еще более случайную" последовательность.
Часто это не так. Например, известно, что формула Х„+1 = (ах„+ с) шгк( т позволяет получить более или менее хорошие случайные числа. Может ли последовательность, полученная из Х„+1 — — ((аХ„) шск1 (т + Ц + с) шо4 т, (2) быть еще более случайной? Ответ: новая последовательность является менее случайной с большой долей вероятности. Такпм образом, идея потерпела неудачу и при отсутствии какой-нибудь теории о поведении последовательности (2) мы попадаем в область генераторов типа Х„з.1 = У(Х„) с выбранной наудачу функцией /.
В упр. 3.1-11, 3.1-15 показано, что зти последовательности, вероятно, ведут себя намного хуже, чем поюедовательности, полученные при использовании более регулярных функций (1). Давайте рассмотрим другой подход к попытке пазучить подлинно улучшенный вариант последовательности (1). Линейный конгрузнтный метод может быть обобшен, скажем, в квадратичный конгрузнтный меток: Х„+1 = (НХт + аЛ „+ с) шос) т.
В упр. 8 обобщена теорема 3.2.1.2А, чтобы получить необходимые и достаточные условия для а, с и а, такие, чтобы последовательность, определенная соотношением (3), имела период максимальной длины т. В этом случае ограничения не более жесткие, чем в линейном методе, Для т, которое является степенью 2, интересный квадратичный метод предложил Р. Р. Ковэю (В. В.. Сотеуоц).
Пусть Хогаоб4= 2, Х„з.т =Х„(Х„+1) шод2', п > О. (4) Данная последовательность может быть вычислена приблизительно с той же эффективностью„что и (1), без любых беспокойств по поводу переполнения. Этот метод имеет интересную связь с подлинным методом средин квадратов фон Неймана (топ Хецшапп). Если положить г'„равным 2'Л„, так что У„является числом двойной точности, полученным в результате размещения справа е нулей у двоичного представления числа Х„, то 1'„з.1 точно совпадет со средними 2е цифрами 1'„з+ 2'1„) Другими словами, метод Ковэю в некоторой степени почти идентичен вырожденному методу средин квадратов двойной точности, однако ан гарантирует получение длинного периода. Дополнительное свидетельство его случайности приведено в статье Ковэю, цитируемой в ответе к упр. 3. Другие обобщения выражения (1) также очевидны.
Например, можно попытаться увеличить длину периода последовательности. Период линейной конгруэнтной последовательности довольно длинный; когда па приблизительно равно длине слова компьютера, обычно получаются периоды порядка 10» или больше и в типичных вычислениях используется лишь маленькая часть последовательности. С другой стороны, при рассмотрении идеи "'точности" в разделе 3.3.4 получается, что длина периода влияет на степень случайности последовательности.
Значит, желательно получить длинный период и существует несколько подходящих для этого методов. Один из них состоит в том, чтобы сделать Х„+а зависящим от Х„и Л„ы а не только от Х„. Тогда длина периода сможет достичь значения па~, твк как последовательность не станет повторяться, пока не будет получено равенство (Х„+ю Х„.ах+а) = (Х„, Х„+1). Джон Мочли (ЛоЬп МаисЫу) в неопубликованной работе, представленной на статистической конференции в 1949 году, расширил метод средин квадратов с помощью рекуррентного соотношения Л„= середина(Х„-а Хя-»).
Простейшая последовательность, в которой Х„а.г зависит более чем от одного из предылущих значений, -- это последовательность чисел Фибоначчи (5) Х» ы — — (Х„+ Х„а) пюб па. Данный генератор рассматривался в начале 50-х годов, и обычно он дает длину периода, ббльшую, чем щ. Но тесты показывают, что числа, получаемые с помощью рекуррентного соотношения Фибоначчи, безусловно, иедостатиочно случайны, и, таким образом, выражение (5) нас, главным образом, интересует, как элегантный "плохой пример" источника случайных чисел. Можно также рассматривать генераторы вида (б) Ха ы = (Х„+ Х„») щоб па, когда й — сравнительно большое число. Это рекуррентное сооуношение было введено Грином.
Смитом и Клем (Огееп, Бш1»Ь, апб К)егп (У4СМ 8 (1959), 527-537)), сообщившими, что, когда Й < И, тестирование последовательности с ибибдьзовйиием критерия "интервалов", описанного в разделе 3.3.2, дала отрицательный результат, хотя при к = 10 результат был положительным. Намного лучший аддитивньай генератор был изобретен Дж. Ж. Митчелом (С. 3. М1гсЬеИ) и Д. Ф. Муром (П.
Р. Мооге) в 1958 году (не опубликовано), Они предложили несколько необычную последовательность, определенную так: (7) = (Х -»а+ Х»») щодт и > 55 где щ — четное число, а Л»,...,Л»а — произвольные целые не все четные числа. Числа 24 и 55 в данном определении не были выбраны наудачу; зти специальные числа выбраны, оказывается, для того, чтобы определить такую последовательность, младшие значащие двоичные разряды (Х„щоб 2) которой имеют длину периода 2ы — 1. Очевидно, последовательность (Х„) должна иметь период по крайней мере такой же длины. В упр. 30 доказывается, что длина периода последовательности, определенной в выражении (7), точно равна 2' '(2'» — 1), когда пг ы 2'.
На первый взгляд, рекуррентное соотношение (7) кажется не очень удобным для реализации на компьютере, но на самом деле существует эффективный путь генерирования этой последовательности с помощью циклической таблицы. Алгоритм А (Аддигпивнмб генератор чисел). В ячейки памяти У[1], У[2], ..., У[55] записано множество значений Лы, Лаз, ..., Ла соответственно; » вначале равно 24, а»г равно 55. При реализации этого алгоритма на выходе последовательно получаем числа Лы, Лвв,.... А1. [Суммирование.] (Если на выходе мы оказываемся в точке Л"„, то У[у] равно Х„ы, а У[х] равно Л„ы,) Запишем У[)»] +- (У[Ц+ У[Я) шо»12', тогда на выходе получим У[к]. А2.
[Продвижение.] Уменьшим у и й на 1. Если у = О, то присвоим у < — 55; иначе, если й = О, присвоить к «- 55. $ Этот алгоритм на компьютере И1Х имеет следующий вид. Программа А (А ддитивнмб генератор чисел), Если предположить, что индексные регист17ь» 5 и 6, содержащие д и к, не затрагиваются частью программы, в которой эта подпрограмма размещена, то следующий текст программы реализует алгоритм А и заносит результат в регистр А.
»»!».!»!. Ыгюч!и е, АОР Т „б У» + 1» (возможно переполнение) ЯТА Т,б -» У». ОБ»» ! ~~!. !» . !» — !. ОЕС6 1 Й»- У вЂ” 1. дбР «+2 ЕИТб бб Если д = О,присвоить д «- 55. 36Р «+2 ЕИТ6 65 Если й = О, присвоить х+- 55. ! Этот генератор обычно работает быстрее других генераторов, обсуждавшихся ранее, так как он не требует никакого умножения. Кроме большой скорости выполнения этот алгоритм имеет самый длинный период'из тех, которые встречались ранее, за исключением периода из упр. 3.2.1.2 — 22.
Более того, как заметил Ричард Брент (В1сЬаг»( Вгепт), его можно реализовать в режиме работы с плавающей запятой, избегая преобразований целых чисел в дробные числа и наоборот (см. упр. 23). Поэтому можно доказать, что этот генератор является наилучшим источником случайных чисел для достижения практических целей. Основная причина, по которой трудно искренне рекомендовать последовательности, подобнь»е (7), состоит в том, что получено очень мало теоретических результатов, основываясь на которых, можно проверить, имеет ли такая последовательность желаемые случайные свойства.
Учитывая, как уже известно, что длинный период не всегда обеспечивает желаемые свойства, Джон Рейзер (ЛОЬп Ве1аег) (РЬ, В, 1Ьеа1з, бсашоЫ Вп(пега(су, 1977) показал, однако, что аддитивные последовательности, подобные (7), будут в высокой степени хорошо распределень» для больших размерностей, если обеспечить выполнение определенных приемлемых условий (см. упр. 26). Числа 24 и о5 в (7) обычно называют запаздыванием, а числа Х„, определенные в (7), — последовательносгпыо Фибоначчи с запаздыванием. Причины, по которым запаздывания, подобные (24, 55), работают хорошо, следуют из приведенных ниже теоретических результатов. Конечно, до некоторой степени легче использовать бспьшие запаздывания, когда в приложениях случается применять, скажем, группы из 55 чисел одновременно. Среди чисел, генерируемых (7), никогда не найдется Таблица 1 СМЕЩЕНИЯ, ПРИВОДЯЩИЕ К ДЛИННЬ1М ПЕРИОДАМ ПО МОДУЛ1О 2 (24, 65) (37, 100) (83, 258) (273, 607) (576, 3217) (7083, 19937) (38, 89) (30., 127) (107, 378) (1029, 2281) (4187, 9689) (9739, 23209) Раслгиреииые варианты зтоя таблипы привопятсв в работах В, 2!аг1ег апб Л Впйьагг, глГогтапоп алд Сопгго1 13 (1968), 541-554, 14 (1969), 566-569, 15 (1969), 67-69; У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
