Методы получения случайных чисел и их машинная генерация

При построении стохастических имитационных моделей и их исследовании необходимо обеспечить возможность генерирования случайных величин. Для этой цели используются случайные числа, равномерно распределенные в интервале [0,1]. Естественно, что, если имитационная модель просчитывается на ЭВМ, необходимо 1) получать равномерно распределенные случайные числа и 2) использовать эти случайные числа для генерации случайных величин с требуемыми характеристиками.

Заметим, что получить на ЭВМ случайное число, равномерно распределенное в интервале [0,1], строго говоря, в принципе невозможно из-за конечной разрядности любой ЭВМ. Однако отличие получаемых реализаций случайной величины от равномерно распределенной оказывается незначительным для ЭВМ с высокой разрядностью.

Методы получения значений случайной величины, равномерно распределенной в интервале [0,1], можно разделить на три большие группы:

1) Использование физических датчиков (генераторов) случайных чисел.

2) Использование таблиц случайных чисел.

3) Получение псевдослучайных чисел.

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

Общий недостаток физических датчиков случайных чисел – малое быстродействие и невозможность повторения последовательности случайных чисел, что существенно ограничивает область применения этих датчиков.

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

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

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

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

Объем массива чисел псевдослучайной последовательности всегда ограничен. В любой ЭВМ с конечной разрядностью N число возможных значений величины, лежащей в интервале [0,1], составляют (один разряд знаковый). Следовательно, в последовательности чисел рано или поздно появится такое число , которое уже там было. Начиная с этого числа, все предыдущие числа последовательности начнут повторяться.

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

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

Мультипликативный конгруэнтный метод. Метод представляет собой арифметическую процедуру для генерирования конечной последовательности равномерно распределенных чисел. Основная формула метода имеет вид:

где a и m - неотрицательные целые числа. Согласно этому выражению мы должны взять случайное последнее число, умножить его на постоянный коэффициент a и взять модуль полученного числа по m (т.е. разделить на и остаток считать как ). Поэтому для генерирования последовательности чисел необходимы начальное значение , множитель a и модуль m. Эти параметры выбирают так, чтобы обеспечить максимальный период и минимальную корреляцию между генерируемыми числами.

Правильный выбор модуля не зависит от системы счисления, используемой в данной ЭВМ. Для ЭВМ, где применяется двоичная система счисления, (N - число двоичных цифр в машинном слове). Тогда максимальный период (который получается при правильном выборе a и ) равен

(N>2).

Выбор и a зависит также от типа ЭВМ. Для двоичной машины

,

где T может быть любым целым положительным числом, а - любым положительным, но нечетным числом. Следует заметить, что указанный выбор констант ускоряет и упрощает вычисления, но не обеспечивает получение периода максимальной длины. Большой период можно получить, если взять m, равное простому наибольшему числу, которое меньше, чем , и a, равное корню из m. Максимальная длина последовательности будет увеличена от m / 4 до (m - 1). (Метод Хатчинсона). Изложенный алгоритм в виде подпрограммы на языке Фортран с именем RANDU имеется в математическом обеспечении ЭВМ. При этом константы, используемые в подпрограмме, для 32-разрядного машинного слова имеют значения:

a = = 1220703125, 1/m = 0.4656613Е-9.

Смешанные конгруэнтные методы. На основе конгруэнтной формулы были созданы и испытаны десятки генераторов псевдослучайных чисел. Работа этих генераторов основана на использовании формулы

,

где a, c, m - константы, обычно автоматически вычисляемые в подпрограмме.

Грин, Смит и Клем предложили аддитивный конгруэнтный метод. Он основан на использовании рекуррентной формулы

.

При Xo = 0 и = 1 этот алгоритм приводит к особому случаю, называемому последовательностью Фибоначчи.

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

Дата добавления: 2014-01-11