Научно-технический прогресс XX века во многом обязан развитию теории вероятностей и созданию генераторов случайных чисел.
Случайными называют числа, которые могут быть интерпретированы как результаты реализации какой-либо случайной величины — основного понятия теории вероятностей. Понятие случайности в данном контексте предусматривает непредсказуемость значения данной величины до начала эксперимента.
История случайных чисел
Потребность человечества в использовании случайных чисел возникла задолго до изобретения учёными устройств, позволяющих получать случайные массивы. Долгое время для генерации случайных чисел люди пользовались подручными средствами, в том числе объектами живой и неживой природы.
Одним из наиболее ярких примеров простейших генераторов случайных чисел являются всем знакомые игральные кости, находящие широкое применение и в настоящее время. В элементарных и обучающих экспериментах зависимостями закона движения игральной кости от окружающей её среды, начальных условий и человеческого фактора вполне можно пренебречь, поэтому количество очков, выпавших на игральной кости, с некоторыми оговорками можно считать случайной величиной. Игральные кости сыграли существенную роль в развитии теории вероятностей: в 1890 году английским исследователем Фрэнсисом Гальтоном (Francis Galton) был предложен способ генерации случайных чисел с использованием игральных костей.
Чуть более сложен в устройстве ещё один широко применяющийся в обиходе генератор чисел — лототрон. Это устройство представляет собой барабан с пронумерованными шарами, перемешивающимися внутри него при вращении. Основная область применения лототронов — лотереи и лото. Несложно догадаться, что для использования в серьёзных научных экспериментах лототрон непригоден ввиду малой степени случайности и скорости работы.
Первый генератор случайных чисел, позволяющий получать большие массивы данных и пригодный для решения прикладных задач, был изобретён в 1939 году. Морис Джордж Кендалл (Maurice George Kendall) и Бернард Бабингтон-Смит (Bernard Babington Smith) создали устройство, с помощью которого можно было генерировать таблицу, содержащую 100 000 случайных чисел. А всего через 16 лет американской стратегической компанией RAND результаты английских академиков были улучшены в 10 раз — с помощью специальных машин была создана таблица из миллиона случайных чисел. Табличный метод генерации случайных чисел получил существенное развитие благодаря Джорджу Марсалье (George Marsaglia), получившим в 1996 году 650 Мбайт случайных чисел. Однако из-за узости области применения данный метод в настоящее время не имеет широкого признания.
Машины, генерирующие случайные числа в реальном времени, обладают рядом преимуществ по сравнению с устройствами, создающими таблицы случайных чисел. Одной из первых таких машин стал компьютер Ferranti Mark 1, в который в 1951 году была включена программа, генерирующая случайные числа на основе входного потока шума резистора. Интересно, что автором идеи создания подобной программы является великий английский математик Алан Тьюринг (Alan Mathison Turing). Также инновационным в области генерации случайных чисел стало изобретение в 1957 году устройства ERNIE (Electronic Random Number Indicator Equipment), первоначально предназначавшегося для генерации выигрышных номеров в британской лотерее.
Псевдослучайные числа
Изобретение генераторов случайных чисел, несомненно, значительно ускорило научно-технический процесс. Однако эти устройства обладали критически важным недостатком, существенно ограничивающим возможность их применения. Уже в середине XX века венгеро-американский математик Джон фон Нейман (John von Neumann) отмечал непригодность физических генераторов случайных чисел в вычислительной технике, обусловленную невозможностью повторения случайного эксперимента и, как следствие, невозможностью воспроизведения случайного числа для проверки работы машины. Так появилась потребность учёного сообщества в псевдослучайных числах — числах, обладающих рядом важных свойств случайных чисел, однако получаемых не в результате случайного эксперимента, а на основе некоторого алгоритма. Сам Джон фон Нейман стал автором метода «середины квадрата», позволяющего получать на выходе десятизначные псевдослучайные числа.
Основным недостатком псевдослучайных чисел является, безусловно, отсутствие случайности данных, столь важной во многих областях науки и жизнедеятельности. Кроме того, все генераторы псевдослучайных чисел имеют свойство зацикливаться, то есть с некоторого момента повторять последовательность выходных чисел, многие алгоритмы являются обратимыми, а некоторые и вовсе обладают неравномерным одномерным распределением. Поэтому в настоящее время данная область привлекает многих исследователей, стремящихся развить имеющиеся или создать новые эффективные генераторы псевдослучайных чисел.
Интересные факты
- По мнению ряда историков, первые попытки генерации случайных чисел относятся к 3500 году до нашей эры. Связаны они, как ни странно, с древнеегипетской настольной игрой «Сенет», заключающейся в передвижении фишек по доске.
- Долгое время источниками случайных чисел для некоторых реальных практических задач служили результаты переписей населения и других полученных экспериментальным путём таблиц данных.
- Уязвимостью алгоритмов генерации псевдослучайных чисел в начале 2010 годов воспользовался бывший директор по безопасности Multi-State Lottery Association. Нарушитель имел доступ к программному обеспечению, используемому для определения выигрышных номеров лотерейных билетов, с помощью чего мог определять выигрышные комбинации несколько дней в году. В 2015 году после выигрыша размером в 16,5 миллиона долларов ему было предъявлено обвинение.
- Генератор псевдослучайных чисел, установленный на бортовом компьютере одного космического корабля серии «Аполлон» (Apollo), однажды стал причиной сбоев в его движении и серьёзного отклонения от предполагаемой траектории. Как выяснили учёные, выходные данные генератора, использовавшегося для расчёта угловых скоростей, в 80% случаев попадали в нижнюю полуплоскость, что абсолютно не соответствовало требуемым критериям случайности результатов работы генератора.
Проблема генерации случайных чисел в настоящее время является одной из самых актуальных и перспективных в научном сообществе. При этом эта тема в большинстве своём интересна и для людей, далёких от мира науки. Ознакомьтесь самостоятельно с наиболее известными алгоритмами генерации псевдослучайных чисел и областями их использования.
