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

${\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. Такий метод часто реалізують в сучасних системах програмування, хоча він майже непридатний у галузі статистики чи криптографії, де вимоги до «випадковості» значно вищі.

Запропонований Джорджем Марсалією (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}}$[1].

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

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

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

Одні з найновіших генераторів від Джорджа Марсалії. Знову розглядається деяка початкова послідовність, до якої застосовуються операції 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().