AOP_Tom2 (1021737), страница 57
Текст из файла (страница 57)
В разделе 3.2.1.1 выбор ш обсуждается более детально. Вычисление (аХ -ь с) шоб т должно быть пючнмм без округления ошибки. ш) Если т — степень 2 (т. е. если используется дноичный компьютер). выбираем а таким, чтобы а шоб 8 = 5. Если т — степень 10 (т. е, используется десятичный компьютер), выбираем а таким, чтобы а шоб 200 = 21.
Одновременный выбор а и с даст гарантию, что генератор случайных чисел будет вырабатывать все т различных возможных значений Х прежде, чем они начнут повторяться (см. раздел 3.2.1,2), и гарантирует высокий "потенциал" (сьь раздел 3.2.1.3). 1т) Множитель а предпочтительно выбирать между .01тп и .99т, и его двоичные или десятичные цифры не должны иметь простую регуляРную структуРу. Выбирая несколько случайных констант, подобных а = 3141592621 (которые удовлетворяют обоим условиям в (ш)), почти всегда получаем достаточно хороший множитель.
Дополнительная проверка, конечно, нужна, если генератор случайных чисел используется регулярно. Например, частичные отношения не должны быть большими, когда для нахождения пса а и т используется алгоритм Евклида (см. раздел 3.3.3). Множитель должен пройти спектральный критерий (раздел 3.3,4) и несколько критериев, описанных в разделе 3.3.2, прежде чем он получит сертификат качества.
т) Значение с не существенно, когда а -- хороший множитель, за исключением того, что с не должно иметь общего множителя с т, когда т — размер компьютерного слова. Таким образом, можно выбрать с = 1 или с = а. В!нагие используют с = О вместе с гп = 2', но они жертвуют двумя двоичными разрядами точности и половиной начальных значений, чтобы сэкономить всего несколько наносекунд счета (см. упр. 3.2.1.2-9). е1) Младшие значащие цифры (справа) Х не очень случайны, так что решения, основанные на числе Л, всегда должны опираться, главным образом, на старшие значащие цифры.
Обычно лучше считать Х случайной дробью Х/т между 0 и 1, т. е. представлять себе Х с десятичной точкой слева, а не относиться к Х как к случайному целому числу между 0 и т — 1. Чтобы подсчитать случайное целое число между 0 и )с — 1, нужно умножить его на !с (но не делить на АО см. упр, 3.4.1-3) и округлить результат. тй) Важное ограничение случайности последовательности (1) обсуждалось в разделе 3.3.4, в котором показано, что "точность" прн размерности 1 будет только порядка 1/т. Применяя метод А!опте-Карло, необходимо использовать случайные последовательности высокой надежности.
Их можно получить с помощью технических приемов, описанных в разделе 3.2.2. гй1) Можно генерировать не больше т/1000 чисел, иначе последующие будут вести себя подобно предыдущим. Если т = 2зз, значит, новая схема (например, новый множитель а) должна использоваться после генерирования нескольких миллионов случайных чисел. Комментарии, приведенные выше, относятся, главным образом, к машинному языку программирования.
Некоторые понятия прекрасно работают также на языках высокого уровня, например (1) превращается в Х=а«Х+с на языке С, если Х имеет тип беззнаковое длинное и если т равно модулю беззнаково длинной арифметики (обычно 2«з или 2«»). Но С не дает возможности рассматривать Х в качестве дроби, как того требует (х!), если не обращаться к числам с плавающей точкой двойной точности.
Поэтому для языка программирования, подобного С, часто используют другой вариант (1): выбирается простое число т, близкое к наибольшему легко вычисляемому целому числу, а полагается равным первообразному корню т и приращение с в этом случае равняется нулю. Тогда (1) может полностью выполняться простой арифметикой над числами, остающимися между -т и +т, так, как в упр. 3.2.1.1 9. Например, когда а = 48271 и т = 2з1 — 1 (см. строку 20 табл.
3.3.4 — 1), можно вычислить Х +- аХ п1ой т на языке С. В4ет1ае МИ 2147483847 /« простое число Мерсена «/ Вйе11пе АА 48271 /« здесь хорош спектральний критерий «/ Фоеу(ае ЦЦ 44488 /» (1опя)(ИМ/АА) «/ обет!не ВВ 3399 /* ММ Х АА; важно, что ВВ<ЦЦ «/ Х=АА«(Х/ЦЦ)-ВВ«(1опя)(Х/ЦЦ); 1У (Х<0) Х+=ИМ; Здесь Х имеет тнп 1опй и Х можно инициализировать, как ненулевое начальное значение, меньшее МИ. Поскольку ИМ вЂ” простое число, наименьший значащий дво- ичный разряд Х так же случаен, как и самый старший, поэтому в предостережении (т1) нет необходимости.
Чтобы получить миллионы и миллионы случайных чисел, можно скомбинировать эту программу с другой, как в 3.3.4-(38), дописав дополнительно несколько операций. №йет1пе МММ 2147483399 /к простое число, но не Мерсена ч/ №пет1пе ААА 40692 /* другой удачный спектральный критерий ь/ №беу№пе ЦЦЦ 52774 /ч (1опй)(МММ/ААА) ь/ №деутпе ййй 3791 /ь МММ '/ ААА; снова меньше, чем ЦЦЦ ч/ У=АААь(УХЦЦЦ)-йййь(1опй)(У/ЦЦЦ); 11 (7<0) У+=МММ; г=Х-У; 11 (2 =О) 2+=ММ; Подобно Х, случайнан величина У должна быть установлена нс равной нулю. Эти операции несколько отличаются от операций, прин< ~енных в 3.3.4-(38): выходное 2 никогда не равно нулю и Е всегда лежит точно между 0 и 2э|. Длина периода последовательности 2 приблизительно равна 74 квалриллионам, и ее числа сейчас имеют точность, приблизительно вдвое ббльшукз, чем числа Х.
Этот метод мобильный и совершенно простой, но не очень устойчивый. Альтернативная схема, основанная на последовательности Фибоначчи с запаздыванием и вычитанием (упр. 3.2.2-23), даже более привлекательна, так как не только легко преобразуется для использования на разных компьютерах, но значительно быстрее растает н поставляет случайные числа лучшего качества, поскольку 1-мерная точность, возможно, хороша для 1 < 100. Ниже приведена программа на языке С сап,аггау (1опк аа (), 1п1 и), которая генерирует п новых случайных чисел и засылает их в заданный массив аа, испольэун рекуррентное соотношение Л, = (Х, 1ее — Х/ э7) п1ой2~~. (г) Это соотношение, в частности, хорошо подходит для современных компьютеров.
Значение и, должно быть равно по крайней мере 100; рекомендуются большие значения, например 1 000. №пег1пе КК 100 /ч длинное запаздывание ь/ №йет1пе Е1 37 /ь короткое запаздывание */ №8е11пе ММ (11«30) /ь модуль ь/ №оет"1пе шой 41тт(х,у) (((х)-(у))А(ММ-1)) /ь (х-у) шод ММ ч/ 1опя гав х[КК]; /» состояние генератора ь/ чоЫ гап аггау(1авй аа[],1пс п) ( гейтетег Апт уог Ц=О;)<ККЦ++) ааЦ]=гав хЦ]; Хог (Ц<пЦ++) ааЦ]=шоб Пут" (ааЦ-КК],аале-ь(]); уог (1=0;1<11;1++,]++) гап х[1]=пой №Ж(ааЦ вЂ” КК],ааЦ-ьь]); Хог (;1<КК;1++,)++) гап х[1]=пой йту(ааЦ-КК],гвл х[1-1ь]); Вся информация о числах, которые генерируются путем заблаговременного обращения к сап аггау, появляется в массиве гап х. Так, этот массив можно ско- пировать во время вычислений, чтобы позднее повторить запуск программы с такими же значениями, не проходя весь путь назад, к началу последовательности.
Особенностью использования рекуррентных соотношений, подобных (2), является, конечно, необходимость получения сразу всех начальных значений путем присвоения подходящих значений Хе, ...., Хпп. Следующая программа гап айаг((1опй пееп() хорошо запускает генератор, когда задано любое начальное число, находящееся между 0 и 2пе — 3 = 1,073,741,821 включительно. №бет1пе ТТ 70 /« гарантирует разделение потоков «/ №де11пе 1в оЫ(х) ((х)й1) /« блок двоичных разрядов х «/ №бет№пе ечеп№ее(х) ((х)а(ММ-2)) /« делаен х четнын «/ чо14 гап впагп(1опб вееб) [ /« используется для размещения гвл аггау «/ геб№всег 1пт с Ц; 1опб х[КК+КК-13; /« подготовка буфера «/ гей№вгег 1опб вв=ечеп1ге(вееб+2); Тот Ц=ОЦ<ККЦ««) [ хЦ]=вв; вв«=1; йг (вв>=ММ) вв-=ММ-2; /« санозагрузка буфера «/ /« циклический сдвиг 29 двоичных разрядов «/ Тот (Ц<КК+КК-1Ц++) хЦ3=0; х [1]++; /« делаем х[1] (и только х[13) нечетным «/ вв=вееав(ММ-1); с=ТТ-1; чЬ11е (т) [ тот (]=кк-1ц>Оц — ) хЦ+33=хц]; /« "квадрат" «/ тот Ц=КК+КК вЂ” 2Ц>КК-(1Ц-=2) х[КК+КК-1-3]=ечеп1яе(хЦ]); гог Ц=КК+КК-2;3>=ККЦ вЂ” ) И(№е опЫ(хЦ])) ( х[3-(КК-(Ц]=иод дШ(хЦ-(КК-(1.)],х[3]); х Ц -КК3 =поп( 61гт (х Ц -КК], х Ц 3 ); 11 (1в оба( )) [ /« «умнояаен на и« «/ тот (]=ККЦ>ОЦ--) хЦ3=хЦ-13 х [03 =х [КК3; /«сдвягаен буфер циклично «/ йт (Тв ооо(х[КК])) х[(.1]=ноб п(Ш(х[(.(.],х[КК]); И (вв) вв»«1; е1ве т —; Тог (3«ОЦ<ЬЕ;5++) гап хЦ«КК-Ш=х[53; Тот (Ц<КК;5++) гвл х[3-1(]=к[Э]; Довольно любопытное маневрирование гап п(агй приведено в упр.
9, в котором доказывается, что последовательности чисел, генерируемых с различными начальными значениями, независимы: каждый блок 100 последовательных значений Х„, Х «и ..., Х„«пп в последующем выходном массиве гап аггау будет отличаться от блоков, появляющихся с другим начальным значением. (Строго говоря, известно, что это справедливо только тогда, когда и < 2~е, но меньше 2пп нс в год.) Некоторые процессы можно, следовательно, запускать параллельно с различными начальными значениями и быть уверенным, что онн дадут независимые результаты. Разные группы ученых, работающих нвд задачей в различных компьютерных центрах, могут быть уверены, что они не дублируют работу других ученых, если присваивают различные начальные значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
