Как работает random()?
Каждый язык имеет функцию random() или что-то подобное для генерации псевдослучайного числа. Мне интересно, что происходит под генерацией этих чисел? Я не программирую ничего, что делает это знание необходимым, просто пытаюсь удовлетворить свое собственное любопытство.
7 ответов
Вся первая глава основополагающей работы Дональда Кнута " Получисленные алгоритмы" посвящена теме генерации случайных чисел. Я действительно не думаю, что SO-ответ приблизится к описанию проблем. Читать книгу.
Оказывается, на удивление легко получить псевдослучайные числа на полпорядке. В течение десятилетий золотой стандарт был удивительно простым алгоритмом: сохраняйте состояние x, умножайте на константу A (32x32 => 64 бита), затем добавляйте константу B, а затем возвращайте младшие 32 бита, которые также становятся новым x. Если A и B выбраны тщательно, это на самом деле работает довольно хорошо.
Псевдослучайные числа также должны быть повторяемыми, чтобы воспроизвести поведение во время отладки. Таким образом, во время отладки обычно избегают заполнения генератора (инициализация x, скажем, временем суток).
В последние годы и с появлением большего количества вычислительных циклов, доступных для записи, стали доступны более сложные алгоритмы, некоторые из которых были изобретены с момента публикации вполне авторитетных Получисленных алгоритмов. Операционные системы также начинают предоставлять аппаратные и сетевые биты энтропии для специализированных криптографических целей.
Страница Википедии - хорошая ссылка.
Фактический используемый алгоритм будет зависеть от языка и реализации языка.
random() - это так называемый генератор псевдослучайных чисел (PRNG). Функция random() в основном реализована как линейный конгруэнтный генератор. Это функция вида X(n+1) (aXn +c) по модулю m. Xn - последовательность порожденных псевдослучайных чисел. Генерируемая последовательность чисел легко угадывается. Этот алгоритм не может быть использован в качестве криптографически безопасного PRNG.
Википедия: Линейный конгруэнтный генератор
И посмотрите на несгибаемые тесты для PRNG PRNG Diehard Tests
Одна вещь, которую вы, возможно, захотите изучить, - это семейство случайных устройств, доступных в некоторых Unix-подобных ОС, таких как Linux и Mac OSX. Например, в Linux ядро собирает энтропию из различных источников в пул, который оно затем использует для заполнения своего генератора псевдослучайных чисел. Энтропия может исходить из различных источников, наиболее заметным из которых является дрожание драйвера устройства от нажатий клавиш, сетевых событий, активности жесткого диска и (больше всего) движений мыши. Помимо этого, существуют другие методы сбора энтропии, некоторые из которых даже полностью реализованы в аппаратном обеспечении. Есть два символьных устройства, которые вы можете получить случайные байты из и в Linux, они ведут себя следующим образом:
- / dev / urandom дает вам постоянный поток байтов, который является очень случайным, но не криптографически безопасным, поскольку он использует любую энтропию, доступную в пуле.
- / dev / random дает вам криптографически безопасные случайные числа, но не дает постоянного потока, поскольку использует энтропию, доступную в пуле, а затем блокирует, пока собирается больше энтропии.
Обратите внимание, что, хотя Mac OSX использует другой метод для PRNG и, следовательно, не блокирует, мои личные тесты (сделанные в колледже) показали, что он немного менее случайен, чем ядро Linux. Конечно, достаточно хорошо, хотя.
Таким образом, в моих проектах, когда мне нужна случайность, я обычно хожу на чтение с одного из случайных устройств, по крайней мере, для начального числа алгоритма в моей программе.
Чтобы точно ответить на ваш ответ, случайная функция предоставляется операционной системой (обычно).
Но то, как операционная система создает эти случайные числа, является специализированной областью в области компьютерных наук. Смотрите, например, вики-страницу, размещенную в ответах выше.
Генератор псевдослучайных чисел (PRNG), также известный как детерминированный генератор случайных битов (DRBG), представляет собой алгоритм генерации последовательности чисел, свойства которой приблизительно соответствуют свойствам последовательностей случайных чисел. Генерируемая ГПСЧ последовательность не является действительно случайной, потому что она полностью определяется начальным значением, называемым начальным числом ГПСЧ (которое может включать действительно случайные значения). Хотя последовательности, которые ближе к действительно случайным, могут быть сгенерированы с помощью аппаратных генераторов случайных чисел, генераторы псевдослучайных чисел важны на практике из-за их скорости генерации чисел и их воспроизводимости.
ГПСЧ занимают центральное место в таких приложениях, как моделирование (например, для метода Монте-Карло), электронные игры (например, для процедурной генерации) и криптография. Криптографические приложения требуют, чтобы выходные данные не были предсказуемы на основе более ранних выходных данных, и необходимы более сложные алгоритмы, которые не наследуют линейность более простых PRNG.
Хорошие статистические свойства являются центральным требованием для вывода PRNG. В общем, требуется тщательный математический анализ, чтобы быть уверенным в том, что PRNG генерирует числа, которые достаточно близки к случайным, чтобы соответствовать предполагаемому использованию. Джон фон Нейман предупредил о неверном истолковании ГПСЧ как действительно случайного генератора и пошутил, что «любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха».
Вы можете проверить страницу википедии для получения дополнительной информации 1здесь