значениями и быть уверенным, что они дадут независимые результаты. Разные группы ученых, работающих над задачей в различных компьютерных центрах, могут быть уверены, что они не дублируют работу других ученых, если присваивают различные начальные значения. Таким образом, более одного миллиарда практически непересекающихся групп случайных чисел предусмотрено единственными программами ran.array и ran.start. А если этого недостаточно, можете заменить параметры программы 100 и 37 другими значениями из табл. 3.2.2-1.

В программах на языке С для эффективности используется операция "поразрядное и", &, так что их нельзя точно перенести на другие компьютеры, кроме тех, в которых применяется представление с удвоенной точностью целых чисел. Почти все современные компьютеры основаны на арифметике с удвоенной точностью, но для этого алгоритма в действительности операция & не нужна. В упр. 10 показано, как получить такую же последовательность чисел на языке FORTRAN, не используя подобные трюки. Несмотря на то что приведенные здесь программы предназначены для генерирования целых чисел с 30 двоичными разрядами, их легко преобразовать в программы генерирования случайных дробей между О и 1 с 52 двоичными разрядами на компьютерах, имеющих арифметику с плавающей точкой (см. упр. 11).

Вы, возможно, захотите включить программу гап.агтау в библиотеку программ или найти еще кого-нибудь, кто уже так сделал. Один из способов проверки, реализуются ли программы гап.агтау и ran.start в соответствии с операциями, приведенными выше, состоит в запуске следующего элементарного теста программ.

mainO -С register int m; long a[2009] ; ran.start(310952);

for (m=0;m<2009;m++) ran.array(a,1009); printf ( "/.IdXn" , ran x [0] ) ; ran.start(310952);

for (m=0;m<1009;m++) ran.array(a,2009); printf ("7.1d\n", ran x[0]);

Должно быть напечатано 461390032 (дважды).

Предостережение: числа, генерируемые программой ran.array, не удовлетворяют критерию промежутков между днями рождений, приведенному в разделе 3.3.2J, и обладают другими недостатками, которые иногда возникают в высокоточном моделировании (см. упр. 3.3.2-31 и 3.3.2-35). Один из способов избежать проблем, связанных с критерием промежутков между днями рождения, - просто использовать только половину чисел (пропуская нечетные элементы), но это не панацея от других проблем. Лучшая четная процедура, предложенная Мартином Люшером (Martin Liischer), обсуждалась в разделе 3.2.2: используйте программу гап.аггау для генерирования, допустим, 1 009 чисел, но применяйте из них только первые 100 (см. упр. 15). Этот метод теоретически довольно обоснован и не имеет известных недостатков. Большинство пользователей не нуждаются в таком предостережении, но так, определенно, меньше риска и оно позволяет делать выбор между случайностью и скоростью.

Много известно о линейных конгруэнтных последовательностях, подобных (1), но сравнительно мало исследованы свойства случайных последовательностей

Фибоначчи с запаздыванием, подобных (2). Обе, кажется, похожи на практически надежные, если их использовать с учетом приведенных предостережений.

Когда эта глава была написана в конце 60-х годов, поистине ужасный генератор случайных чисел RANDU использовался в большинстве компьютеров мира (см. раздел 3.3.4). Авторы, внесшие большой вклад в науку о генерировании случайных чисел, часто не знали, что обычных методов их доказательств недостаточно. Особенно заслуживает внимания неприятный пример Алана М. Ферренберга (Alan М. Ferrenberg) и его коллег, опубликованный в Physical Review Letters 69 (1992), 3382-3384. Они тестировали свои алгоритмы для трехмерной задачи, рассматривая сначала двумерную задачу с известным ответом, и обнаружили, что предположительно суперкачественные современные генераторы случайных чисел дают неправильные результаты в пятом знаке. А старомодный, как крутящаяся мельница, линейный конгруэнтный генератор X <- 16807Amod (2 - 1) работал прекрасно. Возможно, дополнительные научные исследования покажут, что даже генераторы случайных чисел, рекомендованные здесь, будут неудовлетворительны. Мы надеемся, что этого не случится, но история предупреждает, что нужно быть осмотрительными. Отсюда вытекает наиболее разумная линия поведения - работая с каждой программой метода Монте-Карло, необходимо по крайней мере дважды использовать совершенно различные источники случайных чисел, прежде чем получить решения. Это будет указывать на стабильность результатов, а также оградит от опасного доверия к генераторам со скрытыми недостатками. (Каждый генератор случайных чисел будет "проваливаться" по крайней мере для одной какой-либо задачи.)

Превосходная библиография до 1972 года по генерированию случайного числа составлена Ричардом Нансом и Клодом Оверстритом (мл.) (Richard Е. Nance and Claude Overstreet, Jr., Computing Reviews 13 (1972), 495-508) и Э. P. Совьи (E. R. Sowey, International Stat. Review 40 (1972), 355-371). Период 1972-1984 годов закрыт Совьи в работах International Stat. Review 46 (1978), 89-102; J. Royal Stat. Soc. A149 (1986), 83-107. Последующее развитие обсуждается в книге Шу Тезука (Shu Tezuka, Uniform Random Numbers (Boston: Kluwer, 1995)).

Для подробного изучения использования случайных чисел в численном анализе обратитесь к книге J. М. Hammersley and D. С. Handscomb, Monte Carlo Methods (London: Methuen, 1964). В ней показано, как некоторые численные методы улучшаются с помощью "квазислучайных" чисел, специально предназначенных для определенных целей (необязательно удовлетворяющие статистическим критериям, которые мы обсуждали). Происхождение метода Монте-Карло для компьютеров обсуждается в работе N. Metropolis and R. Eckhardt in Stanislaw Ulam 1909-1984, специальный выпуск Los Alamos Science 15 (1987), 125-136.

Каждому читателю будет интересно рассмотреть упр. 6, приведенное ниже.

УПРАЖНЕНИЯ

1. [21] Используя метод (1), напишите программу со следующими характеристиками для машины MIX.

Вызов последовательности: JMP RANDI

Входные условия: гА = к - положительное целое число < 5000 Выходные условия: гА случайное целое число Y, l<Y<k, все значения равновероятны; гХ =?; переполнение выключено

► 2. [15] Кое-кто напуган тем, что компьютеры в будущем будут править миром, но правительство их "успокаивает заявлениями, что машина не может сделать ничего нового, так как она только повинуется командам ее создателя, программиста. Леди Лавлейс (Lovelace) в 1844 году писала: "Аналитическая машина не претендует на создание чего-либо. Она может сделать все, если известно, как ей приказать это выполнить". Ее утверждение развивалось многими философами. Обсудите это высказывание в связи с генераторами случайных чисел.

3. [32] (Игра в кости.) Напишите программу моделирования бросания двух игральных костей, на каждой из которых выпадают значения 1,2, ...,6с равной вероятностью. Если сумма равна 7 или 11 при первом бросании, то игрок выиграл; если сумма равна 2, 3 или 12, то проиграл. При любой другой сумме называем сумму "очко" и продолжаем бросать игральные кости до тех пор, пока выпадет либо 7 (проигрыш), либо очко (выигрыш).

Играется десять игр. Результат каждого бросания игральных костей можно напечатать в виде го п, где тип - цифры, выпавшие на каждой из двух игральных костей, и сопроводить их соответствующими комментариями (например, "змеиные глаза" либо "маленький солдат", либо "трудная дорога" и т. д.).

4. [40] (Солитер, или пасьянс.) Уйма драгоценного времени уходит на раскладывание пасьянса, и, возможно, автоматика существенно вторгнется в эту область. Напишите программу, которая (i) тасует модель колоды карт; (ii) раскладывает несколько обычных пасьянсов, основанных на порядке карт в колоде, и (iii) выводит на дисплей результат игры, показывая, насколько близко программа подходит к выигрышу. Сохраните собранные статистические данные. Программа по запросу может начать жульничать.

5. [46] (Литературное творчество компьютера.) Телевизионная программа "Думающая машина" была показана по телесети CBS 26 октября 1960 года. Среди всего прочего она отвела важнейшее место двум небольшим пьесам в стиле "вестерн", написанных компьютером. Здесь помещены два сценария в том виде, в каком они были напечатаны компьютером.

Сценарий #1. (Револьвер в правой руке, деньги в левой руке, стакан на столе, бутылка на столе, кобура на грабителе, револьвер шерифа в правой руке шерифа, кобура шерифа на шерифе.)

ГРАБИТЕЛЬ: (Грабитель за окном.) Идет к двери; открывает дверь; входит; закрывает дверь; идет в угол; кладет в углу деньги; идет к столу; кладет револьвер на стол; сидит и ерзает; сидит за столом; берет стакан правой рукой (пустай); ставит стакан на стол; берет бутылку правой рукой; наливает; ставит бутылку на стол; берет стакан правой рукой; пьет из стакана; ставит стакан на стол; берет бутылку правой рукой; сидит за столом; сидит за столом; идет в угол; идет к окну; идет к столу; ставит бутылку на стол; сидит и ерзает; сидит за столом; сидит и ерзает; идет к окну; идет к столу; подымает стакан правой рукой.

ШЕРИФ: (Шериф за окном.) Видит грабителя (грабитель видит шерифа); идет к двери.

ГРАБИТЕЛЬ: Ставит стакан на стол; берет револьвер правой рукой; проверяет револьвер.

ШЕРИФ: Ждет; открывает двери; видит грабителя (грабитель видит шерифа); входит.

ГРАБИТЕЛЬ: Идет к окну; целится; стреляет; ШЕРИФ ЛЕГКО РАНЕН. ШЕРИФ: Идет к окну; целится; стреляет; ПРОМАХНУЛСЯ; идет к двери; идет к окну.

ГРАБИТЕЛЬ: Идет к двери; целится; целится. ШЕРИФ: Целится; стреляет; ПРОМАХНУЛСЯ. ГРАБИТЕЛЬ: Стреляет; ШЕРИФ ЛЕГКО РАНЕН.

ШЕРИФ: Идет к двери; целится; стреляет; ПРОМАХНУЛСЯ; выходит; целится.