Науково-технічний прогрес XX століття багато в чому завдячує розвитку теорії ймовірностей та створенню генераторів випадкових чисел.
Випадковими називають числа, які можуть бути інтерпретовані як результати реалізації будь-якої випадкової величини - основного поняття теорії ймовірностей. Поняття випадковості у цьому контексті передбачає непередбачуваність значення цієї величини до початку експерименту.
Історія випадкових чисел
Потреба людства у використанні випадкових чисел виникла задовго до винаходу вченими пристроїв, що дозволяють отримувати випадкові масиви. Довгий час для генерації випадкових чисел люди користувалися підручними засобами, у тому числі об'єктами живої та неживої природи.
Одним із найяскравіших прикладів найпростіших генераторів випадкових чисел є всім знайомі гральні кістки, що знаходять широке застосування і нині. У елементарних і навчальних експериментах залежностями закону руху гральної кістки від навколишнього середовища, початкових умов і людського чинника цілком можна знехтувати, тому кількість очок, що випали на гральній кістці, з деякими застереженнями можна вважати випадковою величиною. Гральні кістки відіграли істотну роль у розвитку теорії ймовірностей: у 1890 році англійським дослідником Френсісом Гальтоном (Francis Galton) було запропоновано спосіб генерації випадкових чисел з використанням гральних кісток.
Трохи складніший у пристрої ще один генератор чисел, що широко застосовується в побуті, — лототрон. Цей пристрій є барабаном з пронумерованими кулями, що перемішуються всередині нього при обертанні. Основна сфера застосування лототронів - лотереї та лото. Неважко здогадатися, що для використання в серйозних наукових експериментах лототрон непридатний через малу міру випадковості та швидкості роботи.
Перший генератор випадкових чисел, що дозволяє отримувати великі масиви даних та придатний для вирішення прикладних завдань, був винайдений у 1939 році. Моріс Джордж Кендалл та Бернард Бабінгтон-Сміт створили пристрій, за допомогою якого можна було генерувати таблицю, що містить 100 000 випадкових чисел. А лише через 16 років американською стратегічною компанією RAND результати англійських академіків були покращені в 10 разів – за допомогою спеціальних машин було створено таблицю з мільйона випадкових чисел. Табличний метод генерації випадкових чисел отримав суттєвий розвиток завдяки Джорджу Марсальє, який отримав 1996 року 650 Мбайт випадкових чисел. Однак через вузькість сфери застосування даний метод в даний час не має широкого визнання.
Машини, що генерують випадкові числа в реальному часі, мають ряд переваг у порівнянні з пристроями, що створюють таблиці випадкових чисел. Однією з перших таких машин став комп'ютер Ferranti Mark 1, до якого в 1951 році було включено програму, що генерує випадкові числа на основі вхідного потоку шуму резистора. Цікаво, що автором ідеї створення такої програми є великий англійський математик Алан Тьюрінг. Також інноваційним у галузі генерації випадкових чисел став винахід у 1957 році пристрою ERNIE (Electronic Random Number Indicator Equipment), що спочатку призначався для генерації виграшних номерів у британській лотереї.
Псевдовипадкові числа
Винахід генераторів випадкових чисел, безсумнівно, значно прискорив науково-технічний процес. Однак ці пристрої мали критично важливий недолік, що істотно обмежує можливість їх застосування. Вже в середині XX століття угорсько-американський математик Джон фон Нейман наголошував на непридатності фізичних генераторів випадкових чисел у обчислювальній техніці, обумовлену неможливістю повторення випадкового експерименту і, як наслідок, неможливістю відтворення випадкового числа для перевірки роботи машини. Так з'явилася потреба вченого співтовариства в псевдовипадкових числах — числах, які мають ряд важливих властивостей випадкових чисел, проте одержуються не в результаті випадкового експерименту, а на основі деякого алгоритму. Сам Джон фон Нейман став автором методу «середини квадрата», що дозволяє отримувати десятицифрові псевдовипадкові числа на виході.
Основним недоліком псевдовипадкових чисел є, безумовно, відсутність випадковості даних, такої важливої у багатьох галузях науки та життєдіяльності. Крім того, всі генератори псевдовипадкових чисел мають властивість зациклюватися, тобто з деякого моменту повторювати послідовність вихідних чисел, багато алгоритмів є оборотними, а деякі взагалі мають нерівномірний одномірний розподіл. Тому в даний час ця область залучає багатьох дослідників, які прагнуть розвинути наявні або створити нові ефективні генератори псевдовипадкових чисел.
Цікаві факти
- На думку ряду істориків, перші спроби генерації випадкових чисел відносяться до 3500 до нашої ери. Пов'язані вони, як не дивно, з давньоєгипетською настільною грою Сенет, що полягає в пересуванні фішок по дошці.
- Довгий час джерелами випадкових чисел для деяких реальних практичних завдань були результати переписів населення та інших отриманих експериментальним шляхом таблиць даних.
- Уразливістю алгоритмів генерації псевдовипадкових чисел на початку 2010 років скористався колишній безпековий директор Multi-State Lottery Association. Порушник мав доступ до програмного забезпечення, яке використовується для визначення виграшних номерів лотерейних квитків, за допомогою чого міг визначати виграшні комбінації кілька днів на рік. У 2015 році після виграшу розміром 16,5 мільйона доларів йому було пред'явлено звинувачення.
- Генератор псевдовипадкових чисел, встановлений на бортовому комп'ютері одного космічного корабля серії Apollo, став причиною збоїв у його русі і серйозного відхилення від передбачуваної траєкторії. Як з'ясували вчені, вихідні дані генератора, що використовувався для розрахунку кутових швидкостей, у 80% випадків потрапляли в нижню напівплощину, що абсолютно не відповідало необхідним критеріям випадковості результатів роботи генератора.
Проблема генерації випадкових чисел наразі є однією з найактуальніших та найперспективніших у науковій спільноті. При цьому ця тема здебільшого цікава і для людей, далеких від світу науки. Ознайомтеся самостійно з найбільш відомими алгоритмами генерації псевдовипадкових чисел та областями їх використання.
