Алгоритмы получения псевдослучаных чисел

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

Алгоритмы 1-го порядка вида:

_n-1 = Ф (_n) . (1.3.1)

Первый порядок означает, что каждое последующее псевдослучайное число зависит от одного предыдущего. Большинство алгоритмов, используемых на практике, представляют собой рекуррентные соотношения вида (1). В них задается начальное число ₀ и функция Ф(х), с помощью которой получают последовательность псевдослучайных чисел.

Часто используется функция вида D [хg] при больших g (D - дробная часть произведения).

Алгоритмы всегда порождают периодические последовательности псевдослучайных чисел.

Поскольку в коде любой ЭВМ можно записать конечное число N чисел, заключенных в интервале [0, 1], то рано или поздно некоторое число _L совпадет с ранее полученным числом _l . Тогда в силу формулы (1)

, при i = 1, 2, . . . (1.3.2)

Начиная с псевдослучайного числа с индексом L числа начнут совпадать.

Пусть L - наименьшее число, удовлетворяющее условию (2). Множество чисел ₀, ₁, ₂, . . ._L-1 называются отрезком апериодичности последовательности псевдослучайных чисел.

Число L называют длиной отрезка апериодичности, а разность р = L - l - периодом последовательности псевдослучайных чисел.

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

Алгоритмы порядка r

В этом случае вместо рекуррентных соотношений вида (1) для получения последовательности псевдослучайных чисел используются рекуррентные соотношения, в которых каждое последующее число зависит от r предыдущих: _,где ₀, ₁,..._r-1 - заданные начальные числа датчиков. Алгоритмы данного типа изучены в меньшей степени, чем алгоритмы первого порядка. Считается, что алгоритмы данного типа позволяют получить последовательности псевдослучайных чисел с большей длиной отрезка апериодичности,

Метод возмущений

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

Генератор Лемера

В этом генераторе используется функция вида

, , , = число разрядов в ЭВМ, . -число из интервала (0,1) получается извлечением 24 левых битов и умножением на .

Проверка качества формируемой последовательности псевдослучайных чисел

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

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

Тест проверки частот. Проверяются частоты появления каждой из цифр в таблице случайных цифр, составленной из разрядов всех псевдослучайных чисел в порядке их реализации.

Тест проверки пар. С помощью теста проверяются частоты появления различных двузначных чисел среди всех пар цифр.

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

Тест проверки интервалов

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

Тест проверки комбинаций

Проверяется частоты появления различных 4-х или 8-ми разрядных комбинаций цифр в таблице.

Все проводимые проверки частот основаны на использовании критерия Пирсона ².