Требования к генератору случайных чисел

Прежде чем перейти к описанию конкретных алгоритмов получения на ЭВМ последовательностей псевдослучайных чисел, сформулируем набор требований, которым должен удовлетворять идеальный генератор. Полученные с помощью идеального генератора псевдослучайные последовательности чисел должны состоять из квазиравномерно распределенных чисел, содержать статистически независимые числа, быть воспроизводимыми, иметь неповторяющиеся числа, получаться с минимальными затратами машинного времени, занимать минимальный объем машинной памяти.

Наибольшее применение в практике моделирования на ЭВМ для генерации последовательностей псевдослучайных чисел находят алгоритмы вида.

представляющие собой рекуррентные соотношения первого порядка, для которых начальное число х₀ и постоянные параметры заданы [36, 37].

Определим качественно требования к виду функции Ф. Например, легко показать, что функция вида (4.9), изображенная на рис.

4.10, а, не может породить хорошую последовательность псевдослучайных чисел х₁₉ х₂, … Действительно, если построить точки с координатами (х₁₉ х₂), (дг₃, х₄) по случайным числам, полученным, например, из таблицы случайных чисел (табл. 4.2), то они будут равномерно распределены в единичном квадрате 0^х,^1, Соответствующие же точки, построенные по числам (х₁₉ Ф (х₂))> (*э> Ф (*4))" •••" располагаются в площади, ограниченной кривой х_|+, = Ф (х,).

Хорошую последовательность случайных чисел может породить только такая функция х_и1 = Ф (х,), график которой достаточно плотно заполняет единичный квадрат. Примером такой функции может служить х₍+_х ~Д{Ах) при больших целых положительных А_у где Д (и) = и—Ц (и) — дробная часть числа и; Ц (и) — целая часть числа и, т. е. наибольшее целое число, не превосходящее и. Пусть для примера А = 10, тогда функция х,₊|=Ф (х/) будет иметь вид, показанный на рис. 4.10, б. Приведенные условия являются только необходимыми, но не достаточными для того, чтобы соотношение (4.9) порождало хорошие последовательности псевдослучайных чисел.

Рассмотрим некоторые процедуры получения последовательностей псевдослучайных квазиравномерно распределенных чисел, которые нашли применение в практике статистического моделирования систем на ЭВМ.

Одной из исторически первых процедур получения псевдослучайных чисел была процедура, получившая название метода серединных квадратов. Пусть имеется 2л-разрядное число, меньшее 1: х*=0, а_А а₂ …02л* Возведем его в квадрат: х² = 0, Ь_х Ь₂ … Ьа"_у а затем отберем средние 2л разрядов х_/+1 =0, Ь_я+_Х Ь"+₂ ••• Ь_3пу которые и будут являться очередным числом псевдослучайной последовательности. Например, если начальное число дг_о=0,2152, то (х₀)² = 0,4 631 104, т. е. =0,6311, затем (х₂)^г=0,39 828 721, т. е. х₂ ⁼ 0*8287, и т. д.

Недостаток этого метода — наличие корреляции между числами последовательности, а в ряде случаев случайность вообще может отсутствовать. Например, если х₀=0,4500, то (х₀)² = 0,20 250 000, х₁ = 0,2500, (х_х)² = 0,6 250 000, *₂ = 0,2500,.

(*₂)² = 0,6 250 000, х₃ = 0,2500 и т. д. Кроме того, при некоторых г* вообще может наблюдаться вырождение последовательности, т. е. дг, = 0 при /^/*. Это существенно ограни;

Ч I.

Рис. 4.10. Вид функции Ф

чивает возможности использования метода серединных квадратов.

Конгруэнтные процедуры генерации. Широкое применение при моделировании систем на ЭВМ получили конгруэнтные процедуры генерации псевдослучайных последовательностей, представляющие собой арифметические операции, в основе которых лежит фундаментальное понятие конгруэнтности. Два целых числа, а и Р конгруэнтны (сравнимы) по модулю т, где т — целое число, тогда и только тогда, когда существует такое целое число к, что а—/?=Ъя, т. е. если разность а-р делится на т и если числа, а и р дают одинаковые остатки от деления на абсолютную величину числа т. Например, 1984=4(шсх110), 5008 = 8(тос110³) и т. д.

Таблица 4.2.

Конгруэнтные процедуры являются чисто детерминированными, так как описываются в виде рекуррентного соотношения, когда функция (4.9) имеет вид.

где Х_(у Х_у Цу М — неотрицательные целые числа. Раскроем рекуррентное соотношение (4.10):

Если заданы начальное значение л₀, множитель Я и аддитивная константа д, то (4.11) однозначно определяет последовательность целых чисел {Л^}, составленную из остатков от деления на М членов последовательности {Х¹Х₀-Ьр (Х¹— 1)/(А — 1)}. Таким образом, для любого 1> 1 справедливо неравенство Х_{<�М. По целым числам последовательности {Л',} можно построить последовательность {*,} = {XJM} рациональных чисел из единичного интервала (0, 1).

Конгруэнтная процедура получения последовательностей псевдослучайных квазиравномерно распределенных чисел может быть реализована мультипликативным либо смешанным методом.

Мультипликативный метод. Задает последовательность неотрицательных целых чисел (ЯГЛ, не превосходящих Л/, по формуле.

т. е. это частный случай соотношения (4.10) при д = 0.

В силу детерминированности метода получаются воспроизводимые последовательности. Требуемый объем машинной памяти при этом минимален, а с вычислительной точки зрения необходим последовательный подсчет произведения двух целых чисел, т. е. выполнение операции, которая быстро реализуется современными ЭВМ.

Для машинной реализации наиболее удобна версия М=р*, где р — число цифр в системе счисления, принятой в ЭВМ (р—2 для двоичной и />= 10 для десятичной машины); g — число битов в машинном слове. Тогда вычисление остатка от деления на М сводится к выделению g младших разрядов делимого, а преобразование целого числа ЛГ, в рациональную дробь из интервала х, е (0, 1) осуществляется подстановкой слева от А', двоичной или десятичной запятой.

Алгоритм построения последовательности для двоичной машины Л/=2* сводится к выполнению таких операций [31, 36, 46]:

• 1. Выбрать в качестве Х₀ произвольное нечетное число.
• 2. Вычислить коэффициент 2=8/±3, где / — любое целое положительное число.
• 3. Найти произведение ХХ₀, содержащее не более 2% значащих разрядов.
• 4. Взять g младших разрядов в качестве первого члена последовательности Л^г₁, а остальные отбросить.
• 5. Определить дробь л;₁ = Л'₁/2* из интервала (0, 1).
• 6. Присвоить Х₀=Х₁.
• 7. Вернуться к п. 3.

Пример 4.4. Необходимо получить числа последовательности для случая ?=4, используя приведенный алгоритм мультипликативного метода. Для этого выполняем следующие действия: 1. Выбираем *о.о-7 (в десятичной системе счисления) или ^₀" =ОИ1 (в двоичной системе счисления). 2. Найдем /— 1, тогда Х₁₀ = И или 5; пусть А₁₀-5, X ="0101. 3. Рассчитываем произведение XX₀, берем g младших разрядов, вычисляем Х_х и присваиваем Х₀**Х_х, т. е. выполняем п. з — 7 алгоритма:

Смешанный метод. Позволяет вычислить последовательность неотрицательных целых чисел {Л')}, не превосходящих М, по формуле.

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

Качество конкретной версии такого генератора можно оценить только с помощью соответствующего машинного эксперимента.

В настоящее время почти все пакеты прикладных программ универсальных ЭВМ для вычисления последовательностей, равномерно распределенных случайных чисел, основанных на конгруэнтной процедуре [17, 38, 40].