Відкрити головне меню

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

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

Вперше запропонував їх використовувати Джон фон Нейман у 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. Архівована копія. Архів оригіналу за 21 вересень 2011. Процитовано 17 грудень 2010.