15. Конгруэнтные методы генерирования случайных чисел.

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

(2.5)

где X_i –i-ый элемент последовательности; , , m - неотрицательные целые числа. Выражение означает, что z есть остаток от деления y на m. Два целых числа X_i+1 и X_i конгруэнтны по модулю m (m – целое) тогда и только тогда, когда существует такое целое к, что X_i+1- X_i = , т.е., если разность X_i+1- X_i делится на m и если числа X_i+1 и X_i дают одинаковые остатки от деления на m.

Если задано начальное значение X₀ , множитель  и аддитивная константа , то по формуле (2.5) можно определить последовательность целых чисел { X₁ ,X₂ ,...,X_i ... }, равномерно распределенных в интервале (0,m). Поделив все числа на m, легко получить последовательность псевдослучайных чисел с равномерным в (0,1) распределением.

Существуют различные конгруэнтные преобразования, которые можно разделить на три группы: 1) мультипликативные, 2) аддитивные, 3) смешанные. Каждый тип преобразования определяет способ генерирования псевдослучайных чисел.

16.Мультипликативный метод.

Мультипликативный конгруэнтный алгоритм задает последовательность неотрицательных целых чисел { X_i }, не превосходящих m, по формуле

(2.6)

представляющей собой частный случай формулы (2.5) при =0. Последовательность, полученная по этому методу, обладает достаточно хорошими статистическими характеристиками. Выбирая параметры  и X₀, с его помощью можно получить последовательность равномерно распределенных некоррелированных псевдослучайных чисел. Более того, при выполнении определенных условий, накладываемых на эти параметры, генерируемая мультипликативная последовательность обладает максимальным при данном модуле m периодом.

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

Для численной реализации наиболее удобна версия алгоритма, в которой модуль m равен , где p - основание системы счисления, используемой в ЭВМ, а l - длина машинного слова.

Выбор m=p^l удобен по двум причинам. Во-первых, вычисление остатка от деления на m сводится к выделению l младших разрядов делимого. Во-вторых, преобразование целого числа X_i в рациональную дробь из интервала (0,1) осуществляется подстановкой слева от него двоичной или десятичной запятой. Таким образом, специальный выбор числа m позволяет исключить из процесса счета две операции деления.

17. Аддитивный метод и смешанный метод.

Аддитивный конгруэнтный алгоритм базируется на следующей формуле:

_{Xi=( Xi-1+ Xi-k)(modm)}

Аддитивные методы используются редко, и характеристики получаемых последовательностей изучены слабо. Модуль m выбирается так же, как и в мультипликативных методах. Период последовательности, получаемый аддитивным алгоритмом, равен , где p_k - постоянная величина, зависящая от k и p. Например, при l=35, p=2, p_k =255, k=16 период равен 255*2³⁴ .

Смешанный метод

Смешанная конгруэнтная процедура вычисляет последовательность неотрицательных целых чисел {X_i}, не превосходящих заданную величину m, по формуле (2.5).

В отличие от мультипликативного метода здесь 0. Преимущество смешанной процедуры в том, что при данном m можно подобрать параметры  и , для которых по формуле (2.5) получается последовательность чисел, с малой степенью корреляции. С вычислительной точки зрения смешанный метод сложнее мультипликативного на одну дополнительную операцию сложения.