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

Матеріал з Вікіпедії — вільної енциклопедії.

Ця стаття не містить посилань на інші статті Вікіпедії. Ви можете допомогти, додавши їх там, де вважаєте за доцільне.

Цю статтю необхідно відформатувати, використовуючи мову розмітки Вікі. Ви можете допомогти проекту, зробивши це!

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

Зміст 1 Лінійний конгруентний метод 2 "Mother-of-All" random number generator 3 Mersenne Twister 4 Генератори типу "Xorshift" 5 Інші генератори

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

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

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

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

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

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

[ред.] Mersenne Twister

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

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

Одні з найновіших генераторів від Джорджа Марсалії. Знову розглядається деяка початкова послідовність, до якої застосовуються операції «Xorshift». Ці операції полягають в наступному: x[i]:= x[i] xor (x[i] shl{ або shr} а). Підсумкове випадкове число може бути одержано за допомогою підсумовування окремих членів послідовності, або застосування до них операції xor. В даний час це один з найбільш використовуваних алгоритмів; послідовність, що генерується, достатньо випадкова, періоди — від (залежно від реалізації), відсутність множень позитивно позначається на швидкості

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

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