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

Такі послідовності називаються псевдовипадковими.

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

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

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

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

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

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

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

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

Квадратичний конгруентний метод

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

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

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

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

«Mother-of-All» random number generator

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

${\displaystyle {\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}}}$ 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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