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

Много примеров случайных чисел можно найти в игровом бизнесе (номера в спортивных лотереях, числа, которые выпадают на рулетке и т.д.). Большинство компьютерных игр также базируется на случайных числах.

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

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

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

Табличный метод. У 1955р. корпорация «Ренд» опубликовала таблицу случайных чисел, которая содержала миллион значений. Для заполнения этих таблиц применялись аппаратные методы. Данные этих таблиц можно использовать при моделировании систем с помощью метода статистических испытаний. Главным недостатком табличного метода является то, что при его использовании расходуются значительные объёмы основной памяти компьютера.

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

Программные генераторы должны удовлетворять таким требованиям:

- генерировать статистически независимые случайные числа, равномерно распределенные на промежутке ;

- иметь возможность воспроизвести заданные последовательности чисел;

- затраты ресурсов процессора на работу генератора должны быть минимальными:

- легко создать независимые последовательности случайных чисел (потоки).

Следует обратить внимание на то, что большинство программных генераторов вырабатывают случайные числа, равномерно распределенные на промежутке . Необходимость моделирования таких чисел обусловлена тем, что на их основе можно получить случайные числа практически любых распределений. Случайные числа, которые вырабатывают программные генераторы, являются квазиравномерно распределенными. Причина в том, что они создаются компьютером, количество двоичных разрядов которого ограничено, и с его помощью можно изобразить только дискретные (а не непрерывные) значения из диапазона от 0 до 1.

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

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

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

Изобразим условно произвольное четырехразрядное десятичное число как . Возведем это число в квадрат и в полученном результате отбросим по две цифры слева и справа.

Четыре цифры, которые остались, и являются новым случайным числом. Если результатом умножения является число с количеством цифр меньше восьми, слева дописывают дополнительные нули.

Пример. Возьмем некоторое число r₀ = 0,1234.

Возведем его в квадрат: r₀² = (0,1234)² = 0,01522756.

Выберем четыре средние цифры этого числа и обозначим их r₁ = 0,5227.

Возведем его в квадрат: r₁² = (0,5227)² = 0,27321529.

Снова выберем четыре средние цифры этого числа и обозначим их r₂ = 0,3215.

Возведем его в квадрат:r₂² = 0,10336225

Далее находим r₃ = 0,3362; r₃² = 0,11303044; r₄ = 0,3030 и т.д.

Последовательность чисел r₁, r₂, r₃, r₄… принимают за последовательность значений случайной величины, распределенной равномерно на промежутке [0; 1].

Реализовать программно этот генератор очень просто, но он имеет ряд недостатков:

- если начальное число четное, то может произойти вырождение последовательности, т.е. начиная с некоторого значения, все последующие числа будут равны нулю (например, если взять начальное число 4500).

- числа, которые вырабатывает генератор, являются сильно коррелируемыми.