Случайности

[enforcer-lt.livejournal.com]

Вопрос будоражит меня уже давно. Как работает функиция random() в различных языках программирования и написанных на их программах? Она действительно выдает абсолютно случайное значение или оно от чего-то таки зависит?
И главынй вопрос: если вызвать эту функцию и посомтреть её значение, а потом гипотетически вернуться в прошлое и вызвать её снова в абсолютно то же время - будет ли результат тем же? А если с отклонением в пару секунд? Допустим мы вызвали функцию и получили 57. А если бы мы вызвали её не сейчас, а через 2 часа, получили бы мы 57?

Comments

[bal.livejournal.com]

Зависит от операционной системы и библиотек. Чаще сегодня - последовательность псевдослучайная, вычисляется по тем или иным алгоритмам, как автономно, так и с влиянием разного рода процессов в ОС. Однако немало случаев использования и аппаратных генераторов случайных чисел, на тех же тепловых шумах.

>а потом гипотетически вернуться в прошлое и вызвать её снова в абсолютно то же время - будет ли результат тем же?

Если генерация числа чисто программная, то, скорее всего, выпадет то же самое число.

Если аппаратная - то тут современная физика дать однозначного ответа не может. Если разрешения квантовых неопределённостей предопределены, то будет то же самое число. Если нет - то, в общем случае, число может быть другим.

[led-mist.livejournal.com]

+ у порограмных генераторов есть seed, который обычно задется автоматически (например время) а можно егo и ручками задавать. так вот если seed совпадает то и вся последовательность сгнерированых чисел будет совпадать. это полезно для воспроизведения всяких simulations.

[led-mist.livejournal.com]

http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

Существуют генераторы случайных и псевдо-

[sanitareugen.livejournal.com]

-случайных чисел.
Основная масса - генераторы псевдослучайных чисел. Где каждое новое число однозначно определяется предыдущим.
Например
x_n+1=(a*x_n+1+b) mod m
где mod - операция взятия остатка.
Это самый распространённый тип ГСЧ (на самом деле псевдослучайных чисел) - простой и дающий выглядящую случайно последовательность. В большинстве случаев этого, при правильном подборе a, b и m - хватает (а как правильно - для начального знакомства Д.Кнут, "Искусство программирования для ЭВМ", т.2, гл. 3)
Иногда, в криптографии или игровом деле, нужно не просто похожее на случайное поведение, а истинная непредсказуемость. Для этого берётся некий случайный источник. Например, радиоактивный распад или тепловой шум - ни тот, ни тот по современным представлениям предсказать нельзя. Подобные источники создавались в большом количестве в 50-х, потом их вытеснили куда более удобные псевдослучайные числа (попробуйте отлаживать программу, если не знаете, чему равны значения переменных), а в последнее время такие устройства стали массово доступны, например, включённые в некоторое материнские платы (в основном для криптографии).
Если желательно использовать псевдослучайные числа, но иметь некоторую непредсказуемость - в качестве начального значения ГСЧ берётся некоторое непредсказуемое число (например, значения миллисекунд часов реального времени на момент вызова программы), для этого служит, например, известная функция randomize.
Еще один источник случайных чисел - таблицы, составленные из физических или демографических наблюдений. Например, известный эксперт по ГСЧ Марсалья издал сборник таких чисел под названием "Чёрно-белый шум" - он выбран из младших битов аудиозаписи рэпа. Это истинно случайные числа, но при повторном обращении к ним мы знаем их значения, что может быть важно для отладки.

Re: Существуют генераторы случайных и псевдо-

[oal.livejournal.com]

Двачую.

Еще скажу, что для всякой криптграфии псевдослучайные числа не очень случайны, поэтому криптожелезо содержит генераторы истиных СЧ. Алсо, то с модулем -- ужас, летящий на крыльях ночи. Но есть и хорошие, но сложные генераторы ПСЧ.

Для отладки принудительно ставят сид, да.

Ну, скомпрометировать, скажем, Mercenne twister...

[sanitareugen.livejournal.com]

...вроде никто не смог. Хотя детерминированный генератор.

Re: Существуют генераторы случайных и псевдо-

[khathi.livejournal.com]

QRBG-121. ^_^
Только сейчас обычно используется не тепловой шум, а шум обратно включённого полупроводникового диода. Он определяется в основном туннельными переходами электронов в двойном заряженном слое p-n-перехода, а это истинно квантовый процесс и как таковой сейчас считается непредсказуемым.

[enforcer-lt.livejournal.com]

Исчерпывающе :)
Т.е., в соверменных компьютерах все предопределнно чем-то. Спасибо.

[joreg.livejournal.com]

http://community.livejournal.com/code_wtf/127108.html?thread=1915012#t1915012

[zellily.livejournal.com]

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

[xen0n.livejournal.com]

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

По кр. мере в OC Linux есть два спецфайла, чтение из который дает случайные числа разного уровня "случайности":
/dev/random (чисто случайные числа. Но при этом чтение из этого файла может заблокироваться пока не появится какое-то событие, на основе которого можно сгенерировать еще случайных чисел)
/dev/urandom (не очень случайные числа, но при этом чтение всегда сразу же возвратит какое-то псевдослучайное число)

http://en.wikipedia.org/wiki/Urandom
http://linux.die.net/man/4/random