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

Конгруэнтные методы генерирования случайных чисел получили наиболее широкое распространение для формирования на ЭВМ псевдослучайных последовательностей.

Два целых числа a и b называются конгруэнтными (сравнимыми) по модулю m, где m – целое число, если разность (a − b) делится на m без остатка, а числа a и b дают одинаковые остатки от деления на m.

Например, 2568 и 148 (по модулю 10), 1746 и 511 (по модулю 5), 6493 и 2221 (по модулю 2) и т.д.

Конгруэнтные методы описываются в виде рекуррентного соотношения следующего вида: X i +1 = λ X i + ё (mod m) (i = 0, 1, 2,...), где X i, λ, ё, m – неотрицательные целые числа; X 0 – начальное значение

псевдослучайной последовательности; λ – множитель; ё – аддитивная константа; m – модуль.

Каждое новое значение X i +1 псевдослучайной последовательности представляет собой целочисленный остаток от деления на модуль m суммы произведения предыдущего значения X i на множитель λ и

аддитивной константы ё. Последовательность псевдослучайных чисел в интервале (0; 1) формируется путем деления полученных целочисленных значений X i на модуль m: xi = X i / m (i = 1, 2,...).

Описанный метод генерирования псевдослучайных чисел получил название смешанного конгруэнтного метода.

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

мультипликативного конгруэнтного метода. В этом случае рекур- рентное соотношение имеет вид X i +1 = λ X i (mod m) (i = 0, 1, 2,...).

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

14. Метод середины квадрата. Общая характеристика, основные недостатки. Требования к функции рекуррентной формулы

Одной из первых арифметических процедур, использованных для вычисления последовательностей равномерно распределенных псевдослучайных чисел, был метод серединных квадратов. В этом методе, предложенным фон Нейманом и Метрополисом в 1946 г., каждое новое число в последовательности получалось взятием средних m цифр из числа, полученного возведением в квадрат первоначального m-значного числа. Метод серединных квадратов состоит из следующих шагов: 1.взять произвольное четырехзначное число. 2.возвести его в квадрат и, если нужно, добавить слева нули до восьмизначного числа. 3. Взять четыре цифры из середины в качестве первого случайного числа. 4.возвести в квадрат четырехзначное число, полученное на щаге 3 (опять при необходимости добавляя слева нули до восьмизначного числа). 5.повторять шаги 3 и 4 до получения необходимого количества случайных чисел.

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

Пусть имеется 2 n -разрядное число, меньше 1:

.

Возведем его в квадрат:

,

а затем возьмем средние 2 n разрядов:

,

которые и будут очередным числом.

Например:

и т.д.

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

К сожалению этот метод трудно проанализировать, он работает сравнительно медленно и не дает статистически удовлетворительных результатов.так, например, корреляцию между первым числом и длиной неповторяющейся последовательности (называемой периодом) заранее оценить очень трудно. Весьма часто последовательность случайных числе может оказаться слишком короткой (или, что хуже, в ней может отсутствовать случайность). Прежняя популярность данного метода простотой описания и легкостью понимания. Можно указать еще такие недостатки: 1. Если какой-нибудь член последовательности окажется равным нулю, то все последующие члены также будут нулями, 2. Последовательности имеют тенденцию " зацикливаться", т. е. в конце концов, образуют цикл, который повторяется бесконечное число раз.

Свойство " зацикливаться" присуще всем последовательностям, построенных по рекуррентной формуле x_i+1=f(x_i).