Соболь И.М. Численные методы Монте-Карло (1973), страница 4

Большинство алгоритмов, используемых на практике дл у я получения псевдослучайных чисел, представляют собой рекуррентные формулы первого порядка у-. =Ф((-) (4) где начальное число ус задано. Легко «: ко показать, ч3о функция у=Ф(х), изображенная на рис. 3, не может у=,(!(агу Рис 3. Рис 4. породить хорош орошую последовагельпость псевдослучайных чисел у!, уг,. В самом деле, если по настоящим слу- чайным числам построить точки с координатами (у!, уз), ( , ),..., о опи равномерно распределены в единич- ном квадрате 0(х(1, 0(у(1, в то время как соот- ветствующие точки, построенные по числам (4), ((! Ф ((1) ) 1(3 Ф ((з) ) ((3 Ф ( !3) ) располагаются на кривой у=Ф(х), С е овательно, «хорошую» последовательность моледовате жет породить только такая фупкцня у=Ф(х), грасрнк которой весь песья!а плотно заполняет единичный квадрат.

Примером такой функции может служить функция д= =Д(дх) при очень больших д (рис. 4). И действитель- но, эта функция послужила основой для ряда методов получения псевдослучайных чисел. Конечно, приведенное условие только необходимо, по далеко не достаточно для того, чтобы формула (4) порождала «хорошие» псевдослучайные числа. Другая важная черта алгоритмов вида (4) — то, что при реализации их на ЭВМ они всегда порождают пе- ПСЕВДОСЛУЧАИНЫЕ ЧИСЛА 21 риодические последовательности.

В самом деле, так как в коде любой ЭВМ можно записать лишь конечное число йг чисел, заключенных между нулем н единицей, то рано или поздно какое-нибудь значение у, совпадает с одним из предыдущих значений уь Тогда в силу (4) у,+ =ум при г=1, 2, ... (5) Пусть 5 — наименьшее число, удовлетворяющее (5) прн некотором 1 (1(Т.); множество чисел То, Ть..., Т -г гг / 3 1 Рг А-(2 йн Рнс. б. называется отрезком анериодичности последовательности (4), число ь' — длиной отрезка анериодичности.

а Р=Š†( — д,тиной периода (рис. 5). Очевидно, в рассматриваемом случае отрезок апернодичпости состоит из различных чисел. И обычно для расчета не рекомендуют использовать больше чем чисел последовательности (4) "). Ясно также, что Т.(Л(. Для экспериментального определения ь и Р можно рекомендовать следующий алгоритм, Выбирается пелое число Т (в несколько раз меньшее, чем предполагаемое значение й). Вычисляются подряд числа уе, уь уг,..., причем уо уг, уэг...

запоминаются, и все у; из отРезка РТ(((~(Р+!) Т сРавннваготсЯ со всеми Уо Уг "° * У г. Как '"'* я ' только окажется выполненным равенство у, = у„,г, вычисляется длина периода Р= и '— глТ и число (=(е — РТ. Чтобы вычислить Т., по числу у< г>г вычисляется у г +, после чего считаются и сравниваются между собой две последовз. тельности значений: У( г)г+. и У( г>г г+ пРи /=й (+г, (+2. Не позднее чем при )'=(+Т произойдет совпадение этих значений. Если совпадение произойдет при )=(е, то (-= (Р†) Т+)ь 2.2. Некоторые конкретные алгоритмы. 2.2.1. Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Вго называют ') Впрочем, использование Е+Р чисел, каи правило, ни к каким осложнениям не приводит, особенно при решении слогкных задач, когда маловероятно, что повторяющееся число будет вторично использовано для моделирования той же величины.

22 ПОЛУЧЕНИЕ СЛУЧАИНЫХ ВЕЛИЧИН НА ЭВМ !ГЛ. ! методом середины квадрата (гп!бб1е-зг!Наге гпейод). В этом методе число у„предполагается 2й-значным: т„=О, а, а,...а„. с!тобы получить число 7„,!, надо у„возвести в квадрат у~ = О, Ь!Ьь... ЬАА н затем о~обрать средние 2й цифр этого квадрата: Тп+1 О ЬА-!! ЬА+2 ". (!м Нетрудно проверить, что этому методу соответствует функция Ф(х) =Д[10 м Ц(!Оыхз)] пли, что то гке, Ф(х) =1О-м Ц[!О" Д(10" х')] Однако от метода середины квадрата вычислители отказались, так как в последовательностях, построенных таким образом, получается больше, чем нужно, малых чисел (см. ниже упражнение 4 гл.

!). Интересно, что при некоторых уь наблюдается вырождение последовательности, т. е. т„— 0 при п)пь. 2.2.2. Наибольшее распространение получил алгоритм, предложенный Д. Д е м е р о и, который называют лгетодом вь!четов (гез!дна! гпейоб) или методом сравнений (сопигпеп1!а! гпейоб). В этом методе Ф(х) = =Д(ух), т. е. (и!.! — Д(и 1 ) (О)', где д — большое целое число, Докажем, что если задать уь в форме несократимой дроби уь ть/М, где т„и М вЂ” цглые числа, и М взаимно просто с у, то все у„будут несократимыми дробял!и вида у„=т„/М, где числители т„определяются форлг улой т„+,— — дт„(гпоб М). (7) Запись (7) означает, что т„, равно остатку, полученному при делении дт„ на М (или, другими словами, т„+! — это наименьший положительный вычет дт„по модулю М).

псввдослучдиныя числя Д о к а з а т е л ь с т в о (по индукции). Пусть у„= тл/М вЂ” несократимая дробь. Тогда яу„=ят„/М. Из (7) следует, что дтл=-гМ-(- +т„н г, где г — целое число. Легко видеть, что т„+, взаимно просто с М В самом деле, если допустить, что у т„+, и М есть общий множитель — простое число 6, толт„должно делиться на 6! но йг делиться на Ь не может, так как л взаимно просто с М; по»гому должно делиться на Й число т„, а зто противоречит предположению о гаы, чзот„/М несократнмая дробь Итак, т„+! взаиглно просго сМи у„, ! —— Д(//ти/М) = Д(г+т„+!/М) = т„+з/М.

На практике обычно используют формулу (7). Изучению последовательностей пт„посвящено много работ. Методами теории чисел удалось исследовать длину отрезка апериодичности (см. упражнение 5 гл. 1) и оценить некоторые величины, аналогичные коэффициентам корреляции между Т и Ч=Ф(Т), между Т и т)=-Ф(Ф(Т)) и т.

п. Однако вопрос о пригодности таких псевдослучайных чисел в конечном счете решается обычными статистическими тестами $ 3, т. е. эмпирически. При некоторых (д, /И, /по) получаются удовлетворительные последовательности, при других — плохие. (См. также гл. 7, п. 3.3.) Удовлетворительная последовательность псевдослучайных чисел получается, например, при д=б'г, /)(=24', то=1 (/.=Р=2чо); результаты статистической проверки этих чисел приведены в 1171). Обширная литература, посвященная ыетоду сравнений, имеется в [69, 139, !40]. Ряд статей с указанием недостатков метода перчнслен в [180]. 2.2.3.

В качестве примера нелинейного алгоритма, используюшего некоторые особенности системы команд ЭВМ, рассмотрим алгоритм, предложенный автором книги для ЭВМ «Стрела». В этом алгоритме число Т„„, получается из числа Т, тремя командами: 1) число Т„умножается на большую константу д; 2) изображение произведения лТ„в ячейке ЭВМ сдвигается на 7 разрядов влево; 3) вычисляется абсолютная величина полученного числа, которая и есть Т„„, (при вычислении абсолютной величины число нормализуется).

ПОЛУЧЕНИЕ СЛУЧАЙНЫХ ВЕЛИ'зин НА ЭВМ [ГЛ Удовлетворительная последовательность псевдослучайных чисел получается, например, при д=! О'т и уо=! (!'.=87835, Р=53535); результаты статистической проверки этих чисел приведены в (751. '1тобы пояснить этот алгоритм, необходимо указать, что в ЭВМ «Стрела» часла представляютсч в нормализованной двоичной форме А=эких гл 2л, где р=1+(((1ок»(х)) — порядок числа, а гл — мантисса (О,б(из<1). Я«ейха ЭВМ, в которую записывается число т, (!1234 31У4.0 611 )Д.В 49 41 41 П~рхйл злах лгл«у«л (!ллх!мггл ,7»л(г аЬп!Уггз! 1'ис. б. состоит из 43 лвоичных разрядов (рис б).

В 1-и разряде записана величина е., которве паже! равнятьса нул!о или единице, и 1 зз э гл =- )' е(2 з, (Л) = ~' ечт 12, !'=! )=в зип х =- ( — 1)"', зяп р = ( — 1)'и (в двоичной записи в!=О, е, е»... е»з, (р) =ем е»в... е„), Если произведению лу„соответствует ячейка [О, е, е»... е«т), то после операции сдпига получаем [еге»...

е„0 0000003. Абсолютная величина этого числа в двоичной записи равна тл+! =О, ее еэ... е«ь Нетрудна проверить, что в случае, когда размещение мантиссы гл и порядка р в ячеике ЭВМ другое, то же чистот„+! можно получить из лу„с помощью двух или трех сдвигов и поразрядного сложения результатов этих сдвигов 2.2.4.

Для получения псевдослучайных чисел на различных ЭВМ используют весьма разнообразные алгоритмы, подобные изложенному в п. 2,23, которые иногда называют способами леремешиваннч. Сведения о них имеются в [19, 69). К сожалению, описание алгоритмов далеко ие всегда сопровождается указанием количества провсренных чисел и тестов, которым зги числа удовлетворяют, или хотя бы уиазанием работ, в которых имеются данные о таких провсрхах. Например, некоторое распространение получил треххомаидиый алгоритм, разработанный Д И.

Голенхо для той же ЭВМ «Стрела». Однако позднее сам автор алгоритма обнаружил ([19), стр. 117), что получаемые этим методом числа плохо удовлетворяют одному из важнейших тестов — проверке пар. псввдослгчАннын чисяА 2.2.5. Из других алгоритмов вида (4) отметим попытки «улучшения» метола вычетов (6) путем рассмотреная функций вила «Р(х) =Д(р+л,х) нли гР (х) = Д ~р+,»,' е х" ~, а=1 где р — заданное дробное число.

Заметного распространения зги методы не получили. 1!гп Р().,г)г'7)( х) = 1 — е Н «ч (8) Д о к а з а т ел ь с т в о, Обозначим записанные числа через уе, уь уз, ... Легко вычислить верон«ио ть того, что Е окажется равным л, где 1(л(М: )у — 1 Л' — 2 у у Л' — (л — 1) л Ф Л(' так как (» (у, ~уз) = ()У вЂ” 1)!Лг, )з(узчьуь узтьу!у Фу«) = ()У вЂ” 2)~'Л', '-Г ун — ~ ~ уо ул — 1+ ул — г~ различны ) Л~ а вероятность того, что у„ совпадет с олиим из различных чисел уь уь ..., у 1, равна н)Л(. 2.3.

Оценка В для алгоритмов вида т„+1= Ф(Т„). 'Для оценки длины отрезка апериодичности, характерного для последовательностей вида (4), можно воспользоваться следующей элементарной вероятностной моделью. Пусть имеется конечное множество, содержащее У различных чисел. Произведем последовательность независимых опытов, в каждом из которых из этого множества извлекается и записывается одно число. Вероятность извлечения каждого числа в каждом из опытов равна 1/Лг (выборка с возвратом).