AOP_Tom2 (1021737), страница 58
Текст из файла (страница 58)
Таким образом, более одного миллиарда практически непересекающихся групп случайных чисел предусмотрено единственными программами гап аггау и гап Иагй А если этого недостаточно, можете заменить параметры программы 100 н 37 другими эначенинмн из табл. 3.2.2 — 1. В программах на языке С для эффективности используется операция "поразрядное и", й, так что их нельзя точно перенести на другие компьютеры, кроме тех, в которых применяется представление с удвоенной точностью целых чисел.
Почти все современные компьютеры основаны на арифметике с удвоенной точностью, но для этого алгоритма в действительности операция й не нужна. В упр. 10 показано, как получить такую же последовательность чисел на языке РОВСАМ, не используя подобные трюки. Несмотря на то что приведенные здесь программы предназначены для генерирования целых чисел с 30 двоичными разрядами, их легко преобразовать в программы генерирования случайных дробей между 0 и 1 с 52 двоичными разрядами на компьютерах, имеющих арифметику с плавающей точкой (см.
упр. 11). Вы, возможно, захотите включить программу гап аггау в библиотеку программ илн найти еще кого-нибудь, кто уже так сделал. Один из способов проверки, реализуются ли программы гап аггау н гап з1аг1 в соответствии с операциями, приведенными выше, состоит в запуске следующего элементарного теста программ. пайпО ( гек1втег Тпрр я; 1опй а[2009]; гап втагс (310952); аког (а=0;а<2009;я++) гап аггау(а,1009); рг1пс1("'/Ы1п", гап х(0]); гап всагт (310952); Хог (в=О;в<1009;а++) гап аггау(а,2009); рг1пкт("Иа1я", гвл х10]); Должно быть напечатано 461390032 (дважды). Предостережение: числа, генерируемые программой гап аггау, не удовлетворяют критерию промежутков между днями рождений, приведенному в разделе 3.3.21, н обладают другими недостатками, которые иногда возникают в высокоточном моделировании (см.
упр. 3,3.2-31 и 3.3.2-35). Один из способов избежать проблем, связанных с критерием промежутков между днями рождения, — просто использовать только половину чисел (пропуская нечетные элементы), но это не панацея от других проблем. Лучшая четная процедура, предложенная Мартином Люшером (Матс!и ЬйвсЬег), обсуждалась в разделе 3.2.2: используйте программу гап аггау для генерирования, допустим, 1 009 чисел, но применяйте из ннх только первые 100 (см.
упр. 15). Этот метод теоретически довольно обоснован и не имеет нзвестных недостатков. Большинство пользователей не нуждаются в таком предостережении, но так, определенно, меньше риска и оно позволяет делать выбор между случайностью н скоростью. Много известно о линейных конгруэнтных последовательностях, подобных (1), но сравнительно мало исследованы свойства случайных последовательностей Фибоначчи с запаздыванием, подобных (2). Обе, кажется, похожи на практически надежные, если их использовать с учетом приведенных предостережений.
Когда эта глава была написана в конце 60-х годов. поистине ужасный генератор случайных чисел ЙА600 использовался в большинстве компьютеров мира (см. раздел 3.3.4). Авторы, внесшие большой вклад в науку о генерирования случайных чисел, часто не знали, что обычных методов их доказательств недостаточно. Особенно заслуживает внимания неприятный пример Алана М. Ферренберга (А!ап М.
ГеггепЬега) и его коллег, опубликованный в РЛув!са! Нек!ев Ьег!егв 69 (1992), 3382- 3384. Они тестировалн свои алгоритмы для трехмерной задачи, рассматривая сначала двумерную задачу с известным ответом, и обнаружили, что предположительно суперкачественные современные генераторы случайных чисел дают неправильные результаты в пятом знаке. А старомодный, как крутящаяся мельница, линейный конгруэнтный генератор Х е- 16807Л' тоб (2зв — 1) работал прекрасно.
Возможно, дополнительные научные исследования покажут, что даже генераторы случайных чисел, рекомендованные здесь, будут неудовлетворительны. Мы надеемся, что этого не случится, но история предупреждает, что нужно быть осмотрительными. Отсюда вытекает наиболее разумная линия поведения — работая с каждой программой метода Монте-Карло, необходимо по крайней мере дважды использовать совершенно различные источники случайных чисел, прежде чем получить решения. Это будет указывать на стабильность результатов, а также оградит от опасного доверия к генераторам со скрытыми недостатками. (Каждый генератор случайных чисел будет "проваливаться' по крайней мере для одной какой-либо задачи.) Превосходная библиография до 1972 года по генерированию случайного числа составлена Ричардом Нвнсом и Клодом Оверстритом (мл.) (Н1сЬагб Е.
Напсе апб С!апаше Охегвтгеев, Лг., Сотрпбпй Нег!ежов 13 (1972), 495 — 508) и Э. Р. Совьи (Е. Н. Вошеу, 1пгегпабопа1 Вгаа Нее!ек 40 (1972), 355 — 371). Период 1972 — 1984 годов закрыт Совьи в работах 1п!егпаг!опа! В!ай Нег!еи 46 (1978), 89-102; 7. Ноучг! 8!аб Вес. А149 (1986), 83-107. Последующее развитие обсуждается в книге Шу Тезука (Яш Техпйа, оп!!огт Нат!от 7титбегв (Нов!оп: К!цшег, 1995)). Для подробного изучения использования случайных чисел в численном анализе обратитесь к книге 1. М. Напппегв1еу апд П. С. НапбвсошЬ, Мопсе Свг1о МеббогЬ (Ьопбоп: МевЬпеп, 1964). В ней показано, как некоторые численные методы улучшаются с помощью "кввзислучайных" чисел, специально предназначенных для определенных целей (необязательно удовлетворяющие статистическим критериям, которые мы обсуждали). Происхождение метода Монте-Карло для компьюте1юв обсуждается в работе Х.
Месгоро!1в апб В.. Ес)сЬагйг ш Вгашв!аш Ь!агп 1909 — 1984, специальный выпуск 1ов А!алюв Яс!енсе 15 (1987), 125-136. Каждому читателю будет интересно рассмотреть упр. 6, приведенное ниже. УПРАЖНЕНИЯ ЗНР йвй01 гА = Л вЂ” положительное целое число < 5000 гА +- случайное целое число 1', 1<1'(!с, все значения равновероятны; гХ =?; переполнение выключено 1. (й!] Используя метод (1), напишите программу соследующими характеристикамидля машины НХХ.
Вызов последовательности: Входные условия: Выходные условия: 2. ]15] Кое-кто напуган тем, что хомпьютеры в будущем будут править миром, но правительство их'успокаивает заявлениями, что машина не может сделать ничего нового, так как она только повинуется командам ее создателя, программиста. Леди Лавлейс (Еоте!асс) в 1644 году писала: "Аналитическая машина не претендует на создание чего-либо.
Она может сделать все, село изеесшно, как ев приказашь это выполнить". Ее утверждение развивалось многими философами. Обсудите зто высказывание в связи с генераторами случайных чисел. 3. ]32] (Игра е клеши.) Напишите программу моделирования бросания двух игральных костей, на каждой из которых выпадают значения 1, 2..., 6 с равной вероятностью Если сумма равна 7 или 11 при первом бросании, то игрок выиграл; если сумма равна 2, 3 или 12, то проиграл. При любой другой сумме называем сумму "очко" и продолжаем бросать игральные кости до тех пор, пока выпадет либо 7 (проигрыш), либо очко (выигрыш). Играется десять игр. Результат каждого бросания игральных костей можно напечатать в виде тп, где гл и п — цифры, выпавшие на каждой из двух игральных костей, и сопроводить нх соответствующими комментариями (напрнмер, "змеиные глаза" либо "маленький солдат", либо "трудная дорога" и т.
д.). 4. ]40] (Солиглер, или пасьянс.) Уйма драгоценного времени уходит на раскладывание пасьянса, и, возможно, автоматика существенно вторгнется в зту область. Напишите программу, которая (1) тасует модель колоды карт; (й) раскладывает несколько обычных пасьянсов, основанных на порядке карт в колоде, и ((п) выводит на дисплей результат игры, показывая, насколько близко программа подходит к выигрышу. Сохраните собранные статистические данные.
Программа по запросу может начать жульничать. б. [46] (Лиглерагпурное творчество компьюгпера.) Телевизионная программа "Думающая машина" была показана по телесети СВБ 26 октября 1960 года. Среди все~о прочего она отвела важнейшее место двум небольшим пьесам в стиле "вестерн", написанных компьютером.
Здесь помещены два сценария в том виде, в каком они были напечатаны компьютером. Сценарий ке1. (Револьвер в правой руке, деньги в левОй руке, Стакан на стОлЕ, бутылка на столе, кобура на грабителе, револьвер шерифа в правой руке шерифа, кобура шерифа на шерифе.) ГРАБи Гель: (Грабитель за окном.) идет к двери; открывает дверь; входит; закрывает дверец идет в угол; кладет в углу деньги; идет к столу; кладет револьвер на стол; сидит и ерзает; сидит за столом; берет стакан правой рукой (пустцй); ставит стакан на стол; берет бутылку правой рукой; наливает; ставит бутылку на стол; берет стакан правой рукой; пьет из стакана; ставит стакан на стол; берет бутылку правой рукой; сидит за столом; сидит за столом; идет в угол; идет к окну; идет к столу, ставит бУтылку на стол; сидит и ерзает; сидит за столом; сидит и еозает; идет к окну; идет к столу; подымает стакан правой рукой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
