2.1. Способи отримання випадкових чисел

– деякі завдання чисельного аналізу;

– імітація  користувацького введення;

– розв’язання задач автентифікації та ідентифікації та ін.

Раніше вчені,яким були потрібні для роботи випадкові числа, розкладали карти, кидали гральні кості, виймали кулі  з урни тощо. Одним з найпростіших механічних приладів для отримання випадкових чисел є рулетка. В першій половині  XX  століття було сконструйовано спеціальні машини, які виробляли випадкові числа механічним шляхом. Зокрема, у 1955 році компанія RAND Corporation опублікувала відомі таблиці з мільйоном випадкових цифр, отриманих такою машиною.

В сучасних умовах для отримання випадкових чисел застосовують різноманітні генератори, які поділяються на дві групи- апаратні (фізичні) та програмні.

Апаратні ГВЧ є пристроями, що перетворюють в цифрову форму який-небудь параметр навколишнього середовища або фізичного процесу, тобто це спеціальні електронні приставки до ЕОМ, які утворюють випадкові числа, використовуючи фізичні явища. Параметр і процес вибираються так, щоб забезпечити хорошу «випадковість» значень при зчитуванні. Дуже часто використовуються  процеси в електроніці (витоки струму, тунельний пробій діодів, цифровий шум відеокамери, шуми на мікрофонному вході звукової карти, радіоактивне випромінювання і т.п.). Для прикладу розглянемо шумлячий радіоелектронний прилад (діод, тріод) та процес радіоактивного випромінювання.

В першому випадку при роботі такого приладу рахуватимемо, скільки разів v за фіксований час Δt напруга перевищила заданий рівень E0. Двійкове випадкове число одержуємо за допомогою співвідношення µ=v mod 2. Якщо частоти появи 0 і 1 рівні, то можна вважати, що пристрій виробляє випадкову послідовність двійкових цифр. Якщо ж частоти не рівні то вводимо яку-небудь схему стабілізації: групування чисел парами, трійками, і т.д. Зазвичай датчики містять декілька генераторів описаного типу, що працюють незалежно один від одного. Отже датчиком видається число , записане у формі m-розрядного двійкового дробу.

Сутність методу, що грунтується на радіоактивному випромінюванні, полягає у слідуючому:

1. Обирається джерело радіоактивного випромінювання з інтенсивністю .

2. Залежно від значення  обирається відрізок часу .

3. За допомогою лічильника визначається кількість часточок, що їх випромінює джерело за час .

4. Застосовується схема:

   1) якщо кількість часточок парна, то = 0;

   2) якщо кількість часточок непарна, то = 1.

Щоб дістати m-розрядне випадкове двійкове число, достатньо m разів звернутися до лічильника радіоактивних часточок.

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

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

Однією з переваг псевдовипадкових чисел є їх швидка генерація, до того ж вони не вимагають пристроїв, що запам'ятовують. Запас псевдовипадкових чисел обмежений. Як стандартні зазвичай використовують рівномірно розподілені на інтервалі [0,1] псевдовипадкові числа.

Більшість алгоритмів обчислення випадкових (псевдовипадкових) чисел, що використовуються при практичних розрахунках, засновані на рекурентних формулах першого порядку: ,  де  ξo  задане.  Що б функція y =ƒ(x) породжувала псевдовипадкові числа, її графік повинен щільно заповнювати квадрат [(0,1)*(0,1)], тобто вона повинна бути розривною в кожній точці. Оскільки рівномірно розподілені випадкові числа повинні задовольняти статистичні вимоги (наприклад, математичне сподівання рівне 0,5, дисперсія рівна 1/12 і т.д.), то умова щільного заповнення всього квадрата є  необхідною. Ще одна особливість алгоритмів типу ξk+1=ƒ(ξk)  полягає в тому, що вони завжди породжують періодичні послідовності. Отже існують такі L і l, що ξL+i=ξl+i, (i=1,2…).

Існує безліч генераторів псевдовипадкових чисел. Приклади алгоритмів отримання псевдовипадкових чисел:

1. Метод середини квадратів.

Одним з перших програмних ГВЧ є метод середини квадратів, запропонований в 1946  р. Джоном фон Нейманом. Цей ГВЧ формує наступний елемент послідовності на основі попереднього шляхом піднесення його до квадрату і виділення середніх цифр отриманого числа. Наприклад, ми хочемо одержати 10-значне число і попереднє число дорівнювало 5772156649. Підносимо його до квадрату і одержуємо 33317792380594909201; це означає, що наступним числом буде 7923805949. Очевидним недоліком цього методу є зациклення у випадку, якщо чергове число буде рівне нулю.

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

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

         x[n+1] = (a x[n]+ c) mod m.                                                   (2.1)

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

Крім лінійних існують інші конгруентні методи. Найвідоміші з них : мультиплікативний, мішаний і адитивний.  Тепер майже всі стандартні бібліотечні програми обчислення послідовності рівномірно розподілених випадкових чисел грунтуються на конгруентних методах.

3. "Mother-of-All" random number generator

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

  S = 21111111111 x[n-4]+1429 x[n-3]+1776 x[n-2]+5115 x[n-1]+c,      (2.2)

                     x[n]= S/232, C = [S/232,] .

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

4. Mersenne Twister

Цей генератор псевдовипадкових чисел ( ГПВЧ) представлений Макуто Матсумото і Такеджі Нушиміро в 1997 р. Основна ідея полягає в тому, що до початкової ітерації, яка ініціює процедуру, застосовується серія бітових операцій. Після їх виконання отримують нову послідовність, перший член якої вважається псевдовипадковим числом. Послідовність має велику розмірність (624 елементи), тому період генератора рівний (219937–1). Існує два загальних варіанти алгоритму, запропонованих авторами, найбільш поширений алгоритм МТ19937. Реалізації цього алгоритму вже використовуються в стандартних бібліотеках для РНР, Python и Рубі. Алгоритм дуже швидкий через відсутність множень, але не має достатньої випадковості. Тому галузь застосування алгоритму дещо обмежена.

5. Генератори типу "Xorshift"

Одні з  генераторів від Джорджа Марсалії. Знову розглядається деяка початкова послідовність, до якої застосовуються операції «Xorshift». Ці операції полягають в наступному:

             x[i]:= x[i] xor (x[i] shl{ або shr} а).                                       (2.3)

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

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

Будь-який генератор псевдовипадкової послідовності (ГПВП) з обмеженими ресурсами рано чи пізно зациклюється. Довжина циклів ГПВП залежить від самого генератора й у середньому становить близько 2(n/2), де n – це розмір внутрішнього стану в бітах, хоча лінійні-конгруентні генератори мають максимальні цикли порядку 2n. Якщо ГПВП може сходитися до занадто коротких циклів, такий ГПВП стає передбачуваним і є непридатним.

Більшість простих арифметичних генераторів хоча й мають велику швидкість, але існує багато серйозних недоліків:

–  занадто короткий період/періоди;

–  послідовні значення не є незалежними;

–  деякі біти “менш випадкові”, ніж інші;

–  нерівномірний одномірний розподіл;

Послідовності випадкових чисел, сформовані тим чи іншим ГВЧ, повинні задовольняти ряд вимог. По-перше, числа повинні вибиратися з певної множини (найчастіше це дійсні числа в інтервалі від 0 до 1 або цілі від 0 до N). По-друге, послідовність повинна підкорятися певному розподілу на заданій множині (найчастіше розподіл рівномірний). Необов'язковою є вимога відтворюваності послідовності. Якщо ГВЧ дозволяє відтворити наново одного разу сформовану послідовність, відладка програм з використанням такого ГВЧ значно спрощується.

Оскільки псевдовипадкові числа не є дійсно випадковими, якість ГВЧ дуже часто оцінюється завдяки “випадковості” одержуваних чисел. У цю оцінку можуть входити різні показники, наприклад, довжина циклу (кількість ітерацій, після якого ГВЧ зациклюється), взаємозалежності між сусідніми числами (можуть виявлятися за допомогою різних методів теорії ймовірності і математичної статистики) і т.п.

Отже, якісний ГПВП має задовольняти такі вимоги:

1.  Непередбачуваність;

2. Добрі статистичні властивості, псевдовипадкова послідовність за своїми статистичними властивостями не повинна істотно відрізнятися від істинної випадкової послідовності;

3.  Великий період формованої послідовності: наприклад, при шифруванні для перетворення кожного елемента вхідної послідовності необхідно використовувати свій елемент псевдовипадкової гами;

4. Ефективна апаратна й програмна реалізація.

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