Перегляд вихідного коду сторінки Генератор псевдовипадкових чисел

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

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

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

== Лінійна змішана форма ==
:<math>x_i = \left( a_0 + \sum_{j=1}^l a_j x_{i-j} \right)\mod m</math>

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

=== Мультиплікативний конгруентний метод ===
:<math>x_i = ( a_1 x_{i-1} )\mod m</math>

{{Розширити розділ|дата=квітень 2010}}

=== Змішаний конгруентний метод ===
:<math>x_{i+1} = (a x_i+c)\mod m</math>

{{Розширити розділ|дата=квітень 2010}}

=== Квадратичний конгруентний метод ===
{{Розширити розділ|дата=квітень 2010}}

== Огляд методів ==

=== Лінійний конгруентний метод ===
{{докладніше|Лінійний конгруентний метод}}

Запропонований Д.&nbsp;Х.&nbsp;Лемером. Основна обчислювальна формула:
: <math>x_{n+1} = (a x_n + c) \mod m</math>

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

=== «Mother-of-All» random number generator ===

Запропонований Джорджем Марсалією (Marsaglia), професором університету Флориди. Обчислювальна формула:
: <math>
\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}
</math>
Цей алгоритм є узагальненням попереднього і позбавлений його головного недоліку&nbsp;— короткого періоду. Його період&nbsp;— <math>2^{250}</math><ref>{{Cite web |url=http://vx.netlux.org/lib/vsl04.html |title=Архівована копія |accessdate=17 грудня 2010 |archiveurl=https://web.archive.org/web/20110921014509/http://vx.netlux.org/lib/vsl04.html |archivedate=21 вересня 2011 |deadurl=yes }}</ref>.

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

=== Вихор Мерсенна ===
{{main|Вихор Мерсенна}}

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

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

=== Генератори типу «Xorshift» ===

Одні з найновіших генераторів від Джорджа Марсалії. Знову розглядається деяка початкова послідовність, до якої застосовуються операції [[xor]] та побітові зсуви. Ці операції полягають в наступному:
: <math>x_n = x_{n-1} \mbox{ xor } (x_{n-1} \mbox{ shl } a)\ </math>

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

Алгоритм має період <math>2^{128}-1</math> та проходить [[тести Diehard]].

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

=== Інші генератори ===

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

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

== Див. також ==
* [[Випадкове просте число]]
* [[Рівномірно розподілена послідовність]]

== Примітки ==
{{reflist}}

{{Crypto-stub}}
{{додаткові джерела|дата=грудень 2018}}

{{ВП-портали|Програмування|Математика}}
[[Категорія:Генератори псевдовипадкових чисел| ]]
[[Категорія:Криптографічні алгоритми]]
[[Категорія:Теорія ймовірностей]]
[[Категорія:Математична статистика]]