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

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

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

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

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

Лінійна змішана форма[ред.ред. код]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вихор Мерсена[en] запропонований у 1997 Макуто Матсумото і Такеджі Нушиміро. Основна ідея полягає в тому, що до початкової ітерації, яка ініціює процедуру, застосовується серія бітових операцій. Після їх виконання отримують нову послідовність, перший член якої вважається псевдовипадковим числом. Цей алгоритм має величезний період: ітерації (це більше ніж ).

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

Генератори типу "Xorshift"[ред.ред. код]

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

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

Алгоритм має період та проходить тести Diehard.

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

Інші генератори[ред.ред. код]

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

Randomize[ред.ред. код]

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

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

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