Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 58
Текст из файла (страница 58)
3.2,1.1-9. Например, когда а = 48271 н т = 2з' — 1 (см. строку 20 табл. 3.3.4 — 1), можно вычислить Х»- аХ шоб гл на языке С. Зйе11пе ИИ 2147483647 /» простое число Иерсена »/ Зает1пе АА 48271 /» здесь хоров сиектральннй критерий »/ Заег1пе ЦЦ 44488 /» (1опй)(ИИ/АА) »/ 44еХАпе йй 3399 /» ИИ Х АА; вакно, что 88<ЦЦ »/ Х=АА»(ХХЦЦ)-88»(1опй)(Х/ЦЦ); 1Х (Х<0) Х+ ИИ; Здесь Х имеет тип 1опй и Х можно инициализировать, как ненулевое начальное значение, меньшее ИИ. Поскольку ИИ вЂ” простое число, наименьший значащий дво- ичный разряд Х так же случаен, как и самый старший, поэтому в предостережении («1) иет необходимости. Чтобы получить миллионы и миллионы случайных чисел, можно скомбинировать эту программу с другой, как в 3.3.4-(38), дописав дополиительио несколько операций. Фоет1ве МММ 2147483399 /« простое число, ыо ие Мерсена «/ Фйе11пе ААА 40692 /« другой удачный спектральный критерий «/ $4е11ве ЦЦЦ 52774 /« (1овй)(МММ/ААА) «/ Вйе11пе ККК 3791 /« МММ / ААА.„ снова неиьне, чеи ЦЦЦ «/ Т ААА«(УХЦЦЦ)-ККК«(1опй)(7/ЦЦЦ)~ 11 (7<0) Т+=МММ; Е=Х"У; 11 (Е<=0) Е+ ММ; Подобно Х, случайная величина У должна быть установлена ие равной нулю.
Эти операции несколько отличаются от операций, прив~ ~сивых в 3.3.4-(38): выходное Е никогда ие равно нулю и Е всегда лежит точно между 0 и 2з|. Длина периода пеледовательиости Е приблизительно равна 74 квалриллиоиам, и ее числа сейчас имеют точность, приблизительно вдвое большую, чем числа Х. Этот метод мобильный и совершенно простой, ио ие очень устойчивый. Альтернативная схема, основанная иа последовательности Фибоиаччи с запаздыванием и вычитанием (упр. 3.2,2-23), даже более привлекательна, так как ие только легко преобразуется для использования нв разных компьютерах, ио значительно быстрее работает и поставляет случайные числа лучшего качества, поскольку 1-мериая точиость, возможно, хороша для 1 < 100. Ниже приведена программа па языке С гап еггау(1опй аа и, (пФ и), которая генерирует и новых случайных чисел и засылает их в заданный массив аа, используя рекурреитиое соотношение Л) = (Ху 1ао — Л„.-зт) шоп 2 (2) Это соотношение, в частности, хорошо подходит для современных компьютеров.
Значение и должно быть равно по крайней мере 100; рекомендуются большие значения, например 1 000. йце11пе КК 100 /«длинное запаздывание «/ $6е11ве Ы. 37 /« короткое запаздывание «/ $6е11пе ММ (11.«30) /«модуль «/ «Ые11пе ио4 6111(х,у) (((х)-(у))А(ММ-1)) /«(х-у) иод ММ «/ 1овй тел х[КК); /« состояние генератора «/ ео14 гап аггау(1опй ааП,1пс и) ( ге81всег Хпс 1,); гог () 0;)<КК;)++) аа[)]=гав х[)); 1ог (;)<и;)++) аа[))=аоб„дШ (аа[)-КК),аа[)-11.)); 1ог (1 0;1<1.1;1++,)++) гап х[1)=вод ЫЖ(аа[)-КК),аа[)-1Ы); 1ог (;1<ХМ;1«+,)««) гап х[1) воа 6Ж(аа[)-КК),гап х[1-Ы) ~ Вся информация о числах, которые генерируются путем заблаговременного обращения к топ аггау, появляется в массиве гол т. Так, этот массив можно ско- пировать во время вычислений, чтобы позднее повторить запуск программы с такима же значениями, не проходя весь путь назад, к началу последовательности. Особенностью использования рекуррентных соотношений, подобных (2), является, конечно, необходимость получения сразу всех начальных значений путем присвое- ниЯ подходащих значений Хо, ..., Хчч.
СледУющаЯ пРогРамма гап.«саг((1опк зева) хорошо запускает генератор, когда задано любое начальное число, находящееся между О и 2зо — 3 = 1,073,741,821 включительно. №бе11ве ТТ 70 /« гарантирует разделение потоков «/ №аеу аб(х) ((х)а1) /«блок двоичных разрядов х «/ №ает1пе ечеп№хе(х) ((х)й(ИИ-2)) /«делаен х четник «/ чо1а гап всагс(1опб аееб) ( /« используется длк разнещения гап аггау «/ гебйасег 1пс с,3; 1опк х[кк+КК-13; /« подготовка буфера «/ гек1асег 1опк ва~ечеп1хе(а«ее+2); тот (3 О'3<КК~3++) ( хЦ3=вв; ае« 1; И (ав> ИИ) ав- ИИ-2; /« санозагрузка буфера «/ /« цвклический сдвиг 29 двоичвнх разрядов «/ Йог (;3<КК+КК-1;3++) к[33=0; х[13++; /« делаем х[13 (и только х[13) и«четник «/ вв вееоа(ИИ-1); с ТТ-1; чк11е (с) ( Тот Ц=КК-1;3>0„3 — ) хЦ+33=хЦ3; /««квадрат««/ 1ог Ц=КК+КК-2;3>КК-ЬЬ;3-=2) х[КК«КК-1"33 ечеп1хе(х[33); Тот (3=КК+Кк-2;3>~кк;)†) И(1а о~И(к[33)) ( х[3-(Кк-ЬЬ))=ива 6111(хЦ-(КК-ЬЬ)3,к[33); хЦ-Кк)=вой 6111(х[3-КК3,х[33); ) 11(1 Ы( )) ( /«»унноиаен на х««/ тот (3=КК; 3 >О; 3 — ) х Ц3 =х [3-13; х [03 =х [КК3; /» сдвигаем буфер циклично «/ 11 (Тв оба(х[КК3)) хПЬ3 иоб„4111(х[ЬЬ),х[КК3); 11 (вв) вв»=1; е1ве С вЂ ; Тот (3~0;3<ЬЬ",3++) гап хЦ+Кк-ЬЬ3«хЦ3; тот (;3<КК;3++) гап х[3-ЬЬ3 хЦ3; Довольно любопытное маневрирование гап Магг приведено в упр.
9, в котором доказывается, что последовательности чисел, генерируемых с различными началь. ными значениями, независимы: каждый блок 100 последовательных значениИ Х„„ Х„+ы, Х„+чч в последующем выходном массиве гап ассар будет отличаться ог блоков, появляющихся с другим начальным значением. (Строго говоря, известно, что это справедливо только тогда, когда и < 2го, но меньше 2зз нс в год.) Некоторые процессы можно, следовательно, запускать параллельно с различными начальными значениями и быть уверенным, что они дадут независимые результаты.
Разные группы ученых, работающих над задачей в различных компьютерных центрах, могут быть уверены, что оии не дублируют работу других ученых, если присваивают различные начальные значения. Таким образом, более одного миллиарда практически непересекающихся групп случайных чисел предусмотрено единственными программами ган аггау и гаи эГагь А если этого недостаточно, можете заменить параметры программы 100 и 37 другими значениями из табл.
3.2.2-1. В программах на языке С для эффективности используется операция "порырядное и", й, так что их нельзя точно перенести на другие компьютеры, кроме тех, в которьпс применяется представление с удвоенной точностью целых чисел. Почти все современные компьютеры основаны на арифметике с удвоенной точностью, но для этого алгоритма в действительности операция й не нужна. В упр.
10 показано, как получить такую же последовательность чисел на языке ГОКТВАХ, не используя подобные трюки. Несмотря иа то что приведенные здесь программы предназначены для генерирования целых чисел с 30 двоичными разрядами, их легко преобразовать в программы генерирования случайных дробей между 0 и 1 с 52 двоичными разрядами на компьютерах, имеющих арифметику с плавающей точкой (см. упр. 11). Вы, возможно, захотите включить программу гоп аггау в библиотеку программ или найти еще кого-нибудь, кто уже так сделал. Один из способов проверки, реализуются ли программы гав аггау и гоп згагг в соответствии с операциями, приведенными выше, состоит в запуске следующего элементарного тестя программ.
ша1пО ( геййвсег 1вс ац 1оцй а(2009); гап есагс (310952); гог (ш=0;ш<2009;ш++) гап аггау(а,1009); рг1цсг("'/1Фп", гвп„х(0)); гап всагс (310952); гог (швО;в<1009;ш++) гэл эггау(а,2009); рг1псг("2151ц", гац х(0)); Должно быть напечатано 461390032 (дважды). Предостережение: числа, генерируемые программой ган аггоу, ие удовлетворяют критерию промежутков между днями рождений, приведенному в разделе 3.3.23, и обладают другими недостатками, которые иногда возникают в высокоточном моделировании (см.
упр. 3.3,2-31 и 3.3.2-35). Один из способов избежать проблем, связанных с критерием промежутков между днями рождения, — просто использовать только половину чисел (пропуская нечетные элементы), но это не панацея от друтих проблем. Лучшая четная процедура, предложенная Мартином Люшером (Магйп Бйэсйег), обсуждалась в разделе 3.2.2: используйте программу гоп аггау для генерирования, допустим, 1 009 чисел, но применяйте из них только первые 100 (см. уцр, 15). Этот метод теоретически довольно обоснован н не имеет известных недостатков.
Большинство пользователей не нуждаются в таком предостережении, но так, определенно, меньше риска и оио позволяет делать выбор между случайностью и скоростью. Много известно о линейных конгруэитных последовательностях, подобных (1), ио сравнительно мало исследованы свойства случайных последовательностей Фибоначчн с запаздыванием, подобных (2). Обе, кажется, похожи на практически надежные, если их использовать с учетом приведенных предостережений. Когда эта глава была написана в конце 60-х годов, поистине ужасный генератор случайных чисел йАИ00 использовался в большинстве компьютеров мира (см, раздел 3.3.4).
Авторы, внесшие большой вклад в науку о генерировании случайных чисел, часто не знали, что обычных методов их доказательств недостаточно. Особенно заслуживает вниманнл неприятный пример Алана М. Ферренберга (А1ап М РепепЬегй) и его коллег, опубликованный в РЬуг0са1 Велев' 1есгегв 69 (1992), 3382- 3384. Они тестировали свои алгоритмы для трехмерной задачи, рассматривая сначала двумерную задачу с известным ответом, и обнаружили, что предположительно суперкачественные современные генераторы случайных чисел дают неправильные результаты в пятом знаке.
А старомодный, как крутящаяся мельница, линейный коигруэнтный генератор Х +- 16807Л шоб (2в' — 1) работал прекрасно. Возможно, дополнительные научные исследования покажут, что даже генераторы случайных чисел, рекомендованные здесь, будут неудовлетворительны. Мы надеемся, что этого не случится, но история предупреждает, что нужно быть осмотрительными. Отсюда вытекает наиболее разумная линия поведения — работая с каждой программой метода Монте-Карло, необходимо по крайней мере двюкды использовать совершенно различные источники случайных чисел, прежде чем получить решения.
Это будет указывать на стабильность результатов, а также оградит от опасного доверия к генераторам со скрытыми недостатками. (Каждый генератор случайных чисел будет "проваливаться" по крайней мере для одной какой-либо задачи.) Превосходная библиография до 1972 года по генерированию случайного числа составлена Ричардом Нщюом и Клодом Оверстритом (мл.) (Н1сЬагс( Е. )л1апсе апб С(апс)е Огегв1геет, Зг., СшпрпНпй Велешв 13 (1972), 495 — 508) и 3. Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
