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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Вперше запропонував їх використовувати Джон фон Нейман у 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} = (a*x_i+c)(mod m)

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

Список методів[ред.ред. код]

Наведемо найбільш прості та відомі з методів генерації псевдовипадкових послідовностей:

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

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

x_{n+1} = (a x_n + c) \mod m

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

"Mother-of-All" random number generator[ред.ред. код]

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


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

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

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

Вихор Мерсена[ред.ред. код]

Докладніше: Вихор Мерсена

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

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

Генератори типу "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(), хоча можна задати початкове число послідовності і вручну.

Посилання[ред.ред. код]

  1. http://vx.netlux.org/lib/vsl04.html