Генератор псевдовипадкових чисел

Можна створити таку послідовність чисел, властивості якої будуть схожі на властивості послідовності випадкових чисел. Такі послідовності називаються псевдовипадковими.

Вперше запропонував їх використовувати Джон фон Нейман у 1946 р. Його метод полягав в наступному: n-розрядне число підносилось до квадрата і з нього вибиралися середні n цифр. Метод був дуже недосконалий, послідовності майже завжди вироджувалися в нуль або зациклювалися з коротким періодом. Пізніше було запропоновано багато різних алгоритмів отримання псевдовипадкових чисел.

В основі програмних генераторів як правило лежать рекурентні формули. Як правило, вони генерують цілі числа рівномірно розподілені на відрізку від 0, до деякого максимального m. Щоб отримати числа з рухомою комою, рівномірно розподілені на [0,1), кожен отриманий результат ділять на m.

Лінійна змішана форма

$x_{i}=\left(a_{0}+\sum _{j=1}^{l}a_{j}x_{i-j}\right)\mod m$

Ця формула має багато часткових випадків:

Мультиплікативний конгруентний метод

$x_{i}=(a_{1}x_{i-1})\mod m$

Змішаний конгруентний метод

$x_{i+1}=(ax_{i}+c)\mod m$

Огляд методів

Лінійний конгруентний метод

Запропонований Д. Х. Лемером. Основна обчислювальна формула:

$x_{n+1}=(ax_{n}+c)\mod m$

Алгоритм зациклюється з періодом, що не перевищує деякого m. Коефіцієнти а, m і x(0) можуть приймати довільні цілі значення, за винятком 0. Параметр с може бути також і 0, але в цьому випадку скорочується період. Число ітерацій m звичайно вибирається рівним максимальному значенню типу, що робить непотрібною операцію ділення, яка автоматично виконається при переповненні. Число а можна взяти рівним, наприклад, 1664525, с — рівним 1013904223. Такий метод часто реалізують в сучасних системах програмування, хоча він майже непридатний у галузі статистики чи криптографії, де вимоги до «випадковості» значно вищі.

«Mother-of-All» random number generator

Запропонований Джорджем Марсалією (Marsaglia), професором університету Флориди. Обчислювальна формула:

${\begin{cases}S=21111111111x_{n-4}+1429x_{n-3}+1776x_{n-2}+5115x_{n-1}+c\\x_{n}={\frac {S}{2^{32}}}\\C=\left[{\frac {S}{2^{32}}}\right]\end{cases}}$

Цей алгоритм є узагальненням попереднього і позбавлений його головного недоліку — короткого періоду. Його період — $2^{250}$.

Випадкове число $x_{i}$ належатиме проміжку [0, 1). Початкові значення можна задавати довільні. Алгоритм може бути застосований в прикладних науках, але він має нижчу швидкість.

Вихор Мерсенна

Вихор Мерсенна запропонований у 1997 Макуто Матсумото і Такеджі Нушиміро. Основна ідея полягає в тому, що до початкової ітерації, яка ініціює процедуру, застосовується серія бітових операцій. Після їх виконання отримують нову послідовність, перший член якої вважається псевдовипадковим числом. Цей алгоритм має величезний період: $2^{19937}-1$ ітерації (це більше ніж $43\times 10^{6000}$).

Алгоритм дуже швидкий через відсутність множень, але не має достатньої випадковості. Тому галузь застосування алгоритму дещо обмежена.

Генератори типу «Xorshift»

Одні з найновіших генераторів від Джорджа Марсалії. Знову розглядається деяка початкова послідовність, до якої застосовуються операції xor та побітові зсуви. Ці операції полягають в наступному:

$x_{n}=x_{n-1}{\mbox{ xor }}(x_{n-1}{\mbox{ shl }}a)\$

Замість shl можна використовувати також shr, та еквівалентне множення.

Алгоритм має період $2^{128}-1$ та проходить тести Diehard.

Підсумкове випадкове число може бути одержано за допомогою підсумовування окремих членів послідовності, або застосування до них операції xor. В наш час^[коли?] це один з найбільш вживаних алгоритмів; послідовність, що генерується, достатньо випадкова, періоди — від (залежно від реалізації), відсутність операцій множення позитивно позначається на швидкості.

Інші генератори

Інтерес можуть представляти комбінації вже представлених методів^{[джерело?]}. Деякі з них реалізовані у відповідних програмних середовищах у вигляді функцій rand(), random().

Randomize

Часто для створення унікальної послідовності псевдовипадкових чисел початковий її член ініціалізують наприклад остачею від ділення поточного часу в мілісекундах на певне число. Зазвичай це робить функція randomize(), хоча можна задати початкове число послідовності і вручну.

Див. також

• Випадкове просте число
• Рівномірно розподілена послідовність