1. Генераторы случайных чисел
Случайныечисла нельзя выработать, используя определённый алгоритм. Однако можно сгенерировать такую последовательность чисел, которая будет приближать многие свойства случайных чисел. Такие числа называются псевдослучайными. Впервые предложил их использовать Джон фон Нейман в 1946 г.
Генератор псевдослучайных чисел –алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному) [1, стр.202].
Внастоящее время существует различные методы генерации случайных чисел. В данной работе автором будут рассмотрены следующие виды: линейный конгруэнтный метод, метод Фибоначчи с запаздыванием, метод Блюм – Блюма – Шуба и метод Вихрь Мерсенна.
1.1. Линейный конгруэнтный метод
Линейный конгруэнтный метод –один из алгоритмов генерации случайных чисел [2]. Данный метод был предложен математиком Д.Г.Лемеров в 1949г. Этот алгоритм заключается в итеративном применении формулы 1.1:
|
|
|
(1.1) |
,
где a, b, c – некоторые константы; ki-1– предыдущее случайное число. Для получения значенияk1задается начальное значениеk0 [2].
1.2 Метод фибоначчи
Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делает невозможным их использование в статистических алгоритмах, требующих высокого разрешения.
Для решения данного недостатка выше указанного метода применяется метод Фибоначчи. Наибольшую популярность датчики Фибоначчи получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а датчики естественно реализуются в вещественной арифметике [3].
Метод Фибоначчи основан итеративной формуле (1.2):
|
|
|
(1.2) |
,
где ki –вещественные числа из диапазона [0,1]; a, b –целые положительные числа, параметры генератора.
Для работы требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел необходим некоторый объем памяти, зависящих от параметров a и b [3].