Почему случайность не так случайна? - PullRequest
4 голосов
/ 11 ноября 2010

Может ли кто-нибудь объяснить, как современные языки программирования (java, c #, python, javascript) справляются с ограничениями случайности и откуда берутся эти ограничения (например, основанные на времени начальные числа).Т.е. если они навязаны базовыми операционными системами и аппаратным обеспечением на базе Intel.

По сути, я хотел бы понять, почему не существует такого понятия, как действительно случайное число без соответствующего аппаратного обеспечения.

Ответы [ 5 ]

8 голосов
/ 11 ноября 2010

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

Чтобы иметь истинный случайный выбор, необходим ввод, который не является детерминированным.1006 *,

Для генерации действительно случайных чисел требуются точные, точные и повторяемые системные измерения абсолютно недетерминированных процессов.Операционная система Linux с открытым исходным кодом использует, например, различные системные временные параметры (такие как нажатия клавиш пользователя, ввод-вывод или измерения напряжения младших разрядов) для создания пула случайных чисел.Он пытается постоянно пополнять пул, в зависимости от уровня важности, и поэтому выдаст случайное число.Эта система является примером и похожа на системы специализированных аппаратных генераторов случайных чисел.

6 голосов
/ 11 ноября 2010

Сначала я собираюсь ответить на вторую часть вашего вопроса:

По сути, я хотел бы понять, почему не существует такого понятия, как действительно случайное число без соответствующего аппаратного обеспечения.

Вы не можете генерировать действительно случайные числа на компьютере без специального оборудования, потому что компьютеры являются детерминированными машинами. Это означает, что, учитывая некоторое начальное состояние и выполняемую операцию, вы можете точно предсказать , как будет развиваться машина. Например, если вы знаете, что в некоторой гипотетической архитектуре этот регистр %d0 содержит 24, а регистр %d1 содержит 42, и вы знаете, что следующая инструкция в потоке инструкций - add %d0 %d1 %d2, тогда вы Знайте, что после выполнения этой инструкции %d2 будет содержать 66. На языке более высокого уровня вы знаете, что написание x = 1; y = 2; z = x + y приведет к , в результате чего z будет 3 с уверенностью.

Это имеет смысл; мы не хотим задаваться вопросом, что будет делать дополнение, мы хотим, чтобы оно добавило . Однако это несовместимо с генерацией действительно случайных чисел. Для того, чтобы число было действительно случайным, должно быть абсолютно никоим образом , чтобы предсказать его, независимо от того, что вы знаете. Некоторые квантово-механические процессы имеют такое поведение точно, а другие естественные процессы достаточно близки к случайным, что для всех практических целей они есть (например, если они выглядят случайными и для их предсказания потребуется знание состояния каждой молекулы в атмосфере ). Тем не менее, компьютеры не могут этого сделать, потому что весь смысл наличия наличия компьютера состоит в том, чтобы иметь машину, которая детерминистически выполняет код. Вы должны быть в состоянии предсказать, что произойдет, когда вы запустите программы, иначе какой смысл?

В комментарии к Милан Рамая ответ , вы сказали

Я согласен с [yo] u, но все еще упускаю самую важную вещь - почему компьютеры не могут выдавать случайное число с предопределенным вводом?

Ответ выпадает прямо из определения действительно случайного числа. Поскольку действительно случайное число должно быть совершенно непредсказуемым, оно может никогда не зависеть от детерминированного ввода. Если у вас есть алгоритм, который принимает заранее определенные входные данные и использует его для получения псевдослучайного числа, вы можете дублировать этот процесс по желанию, лишь бы вы знали входные данные и алгоритм.

Вы также спросили

Может ли кто-нибудь дать объяснение тому, как современные языки программирования… справляются с ограничениями случайности и откуда эти ограничения… происходят.

Ну, как уже упоминалось выше, ограничения присущи детерминированному дизайну наших языков и машин, которые существуют по уважительным причинам (так что упомянутые языки и машины могут использоваться :-)). Предполагая, что вы не обращаетесь к чему-то, что имеет доступ к действительно случайным числам (таким как /dev/random в системах, где это существует), используется следующий подход: использовать генератор псевдослучайных чисел. Эти алгоритмы предназначены для получения статистически случайной выходной последовательности , которая в формальном смысле выглядит непредсказуемой. Я не знаю достаточно статистики, чтобы объяснить или понять детали этого, но я полагаю, что идея состоит в том, что есть определенные числовые тесты, которые вы можете запустить, чтобы сказать, насколько хорошо ваши данные предсказывают себя (в некотором смысле) и тому подобное. Однако важным моментом является то, что, хотя последовательность является детерминированной, она «выглядит случайной». Для многих целей этого достаточно! И иногда это имеет свои преимущества: например, если вы хотите протестировать код, было бы неплохо иметь возможность указать начальное число и всегда получать его одинаковую последовательность псевдослучайных чисел.

ВТаким образом, общий ответ на ваш вопрос таков: поскольку мы хотим иметь возможность прогнозировать, что делают компьютеры, они не могут генерировать непредсказуемые числа (без специального оборудования). Языки программирования, как правило, не слишком подвержены этому влиянию, поскольку генераторы псевдослучайных чисел достаточны для большинства случаев.

1 голос
/ 11 ноября 2010

Системы спроектированы, чтобы быть предсказуемыми и дискретными, никто не хочет хаотичных компьютеров, чтобы люди могли их программировать.Предсказуемые системы не могут производить действительно случайные числа, только предсказуемые числа.

0 голосов
/ 11 ноября 2010

Программные случайные числа имеют два основных шага:
- генерировать псевдослучайное число
- манипулировать этим псевдослучайным числом, чтобы получить число в диапазоне, более полезном (от 0 до 1, от 1 до 100 и т. Д.)

Распространенной проблемой в программных генераторах случайных чисел является то, что всегда есть циклы.Эти циклы состоят из фиксированного набора чисел (алгоритм не может генерировать другие числа). Если алгоритм хорош, то цикл подразумевает очень очень большой набор чисел. Но если алгоритм неправильный, набор чисел может быть недостаточным

Эти сгенерированные числа обрабатываются для получения номеров только от 1 до 100 или от 0 до 1 (например), чтобы они были полезны для вашей программы.Поскольку оригинальный алгоритм не может генерировать все числа в диапазоне, результирующий набор будет получать некоторые числа чаще, чем другие.

0 голосов
/ 11 ноября 2010

Компьютеры генерируют случайные числа, беря их из длинного списка предварительно сгенерированных значений. Использование начального значения помогает создавать разные результаты при каждом запуске программы, но это не все, потому что список фиксирован - он только меняет начальную позицию в этом списке. Компьютеры, очевидно, очень жестки в том, как они делают вещи, потому что они не могут сделать что-то действительно случайное из-за ограничений того, как они сделаны. Такие сайты, как random.org создают случайные числа из внешних источников, таких как радиошум. Может быть, компьютеры должны брать шум от источника питания и использовать его в качестве действительно случайной базы? : -Р

...