Процедуры генерации последовательностей псевдослучайных чисел

Одной из исторически первых процедур получения последовательностей псевдослучайных чисел была процедура, получившая название метода серединных квадратов. Пусть имеется 2n-разрядное число, меньшее единицы: x_i=0,a₁a₂…a_2n. Возведем его в квадрат: x_i²=0,b₁b₂…b_4n, а затем отберем средние 2n разрядов x_i+1=0,b_n+1b_n+2…b_3n, которые и будут являться очередным числом псевдослучайной последовательности. Недостаток данного метода – наличие корреляции между числами последовательности, а в ряде случаев случайность может вообще отсутствовать.

Широкое применение при моделировании систем на ЭВМ получили конгруэнтные процедуры генерации псевдослучайных последовательностей, представляющие собой арифметические операции, в основе которых лежит понятие конгруэнтности. Два целых числа a и b конгруэнтны (сравнимы) по модулю m, где m – целое число, тогда и только тогда, когда существует такое целое число k, что a – b = km, т.е. если разность чисел a и b делится на m и если числа a и bдают одинаковые остатки от деления на абсолютную величину числа m. Конгруэнтные процедуры являются чисто детерминированными, т.к. описываются в виде рекуррентного соотношения:

X_i = lⁱ X₀ + (lⁱ - 1) m / (l - 1) (mod M),

где X_i, l, m, M – неотрицательные целые числа. Если заданы начальное значение X₀, множитель l и аддитивная константа m, то данное соотношение однозначно определяет последовательность целых чисел {X_i}, составленную из остатков деления на M членов последовательности {lⁱ X₀ + (lⁱ - 1) m / (l - 1)}. Таким образом, по целым числам последовательности {X_i} можно построить последовательность {x_i} = {X_i / M} рациональных чисел из интервала (0, 1).