Как работает генератор случайных чисел?

Question

[Никита Паскал]

Здравствуйте! Скажите пожалуйста, есть ли некий алгоритм для получения случайного числа? Скажем, функция rand() в С++. Как она работает? Под простым rand() есть же некий алгоритм. Читал про Генератор псевдослучайных чисел.В целом, более менее понятно для человека, но, как объяснить компьютеру выбери случайное число? То есть, я не понимаю, как выглядит этот алгоритм случайных чисел именно для компьютера? Что значит выбрать случайное число для компьютера?

Answer 1

[ThunderCat]

Читал про Генератор псевдослучайных чисел.

ну почитайте еще

Answer 2

[Adamos]

На самом деле, случайные числа нужны для нескольких целей, и алгоритма, подходящего для всех, нет и быть не может.
Для моделирования может быть важным нормальное распределение выпадающих чисел. Здесь и случайное число по формуле вполне прокатит.
Для игровых целей может быть важна именно высокая случайность числа (то есть, грубо говоря, вероятность выпадения 00000000, 0101010101 и 11111111 одинакова и не зависит от предыдущих выпадений).
Для безопасности обязательна невозможность выведения следующих чисел из предыдущих (или каких-то других условий).

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

Answer 3

[Дмитрий]

rand()в C++ является уязвимым и будет удалён из стандарта.
Сейчас рекомендуется пользоваться реализацией алгоритма Mersenne Twister

Answer 4

[pfg21]

качественный поставщик энтропии еще надо спроектировать доказать его случайность и т.д. и еще есть в нем есть физическое ограничение на скорость выдачи случайных чисел.

Обычно и не нужно таких сложностей, поэтому делается проще - ставится програмный генератор псевдослучайных чисел /dev/urandom, который периодически засеивается "абсолютно" случайным числом.
Кому нужно "абсолютно" случайное число может обращаться напрямую к /dev/random. Но он может исчерпаться и перестать выдавать числа.

отличия хорошо расписаны здесь https://habrahabr.ru/company/mailru/blog/273147/

Answer 5

[entermix]

Все случайные числа на самом деле псевдослучайные

Как работает функция rand в php?

Comments

[Денис Загаевский]

Какое глубокомысленное замечание. А как же RdRand?

[devalone]

Денис Загаевский: это тот, который в современных процессорах intel? Он тоже не случайный и если знать, какие физические процессы происходят в генераторе, то можно предсказать появление нужного бита, но естественно знать этого невозможно, да и мощностей современных компьютеров вряд ли хватит просчитать все эти процессы.

[Денис Загаевский]

devalone: я прям не знаю, вам верить, или Интелу. Они, вот, говорят, что у них источник энтропии честный, хардварный недетерминированный процесс.

3.2.1
The all-digital Entropy Source (ES), also known as a non-deterministic random bit generator (NRBG), provides a serial stream of entropic data in the form of zeroes and ones.

The ES runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz.

Так что знай-не знай процессы, а это настоящий рандом.

[devalone]

Денис Загаевский: да нет, я не спорю, что рандом, я про то, что если смоделировать этот генератор вплоть до атома, то можно было бы предсказать, но смоделировать такое не удастся даже на всех суперкомпьютерах мира :)

[Денис Загаевский]

devalone: нет, дело в том, что это теоретически невозможно. Мешает не количество суперкомпьютеров. Мешает то, что процесс хаотический.

[devalone]

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

[Денис Загаевский]

devalone: я устал с тобой спорить. Что скажешь про кота Шрёдингера?

Answer 6

[Stalker_RED]

Компьютерная программа может генерировать только псевдослучайные числа. Некоторые компьютеры используют аппаратные генераторы случайных чисел. Относительно недавно их стали встраивать в некоторые процессоры.

Answer 7

[res2001]

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

Answer 8

[Mercury13]

Рассказываю на пальцах.
Компьютер запомнил число (или кучу чисел), которое называется «случайная затравка» (random seed).
По команде «сгенерируй случайное число» он проводит два алгоритма.

1. Собственно генератор случайных чисел — преобразование seed → seed.
Например: seed := (37·seed + 234) mod 997.
(знаком :=, как в Паскале, я обозначил «переприсвоить»)

2. Интерпретация результатов: seed → Y*.
Например, y = seed/997.
Y — это [0…1), {1…6} или любое другое желаемое множество.
Y* — множество конечных последовательностей: каждый бросок генератора может не дать ни одного числа (и потребуется переброс), одно число, два числа… Например, наиболее известный генератор нормально распределённых чисел каждым броском даёт или ноль чисел (т.е. нужен переброс), или сразу два.

Затравку надо инициализировать чем-то действительно случайным, и для этого используют таймер, счётчик тактов и прочие труднопредсказуемые места. А ещё можно запомнить затравку и снова повторить ту же последовательность чисел (раньше это использовали для повторов и мультиплеера в играх).

Если же нужны настоящие случайные числа, да в большом количестве — это откровенно тяжело. В ход идут…
• таймеры и счётчики команд — ну, это понятно;
• шум в звуковой плате;
• задержки ввода с клавиатуры и мыши;
• аппаратные датчики случайных чисел на диодном шуме, применяемые в некоторых процессорах.
MacOS, например, этим добром не пользуется; и в dev/random, и в dev/urandom идёт один и тот же криптостойкий псевдослучайных генератор Ярроу.

Answer 9

[devalone]

rand(), емнип, это линейный конгруэнтный метод, плохой, небезопасный для криптографии, но зато быстрый. А так, без внешнего источника "случайности", компьютер не может генерировать случайные для нас числа, т.к. компьютер действует по строго определённой логике, поэтому люди придумывают сложные алгоритмы псевдослучайных чисел, которые выдают последовательность, похожую на случайную, если же нужны действительно случайные числа, то нужно брать их из физических процессов, которые мы предсказать не в силах. Для примера, когда мы бросаем кубик, мы предполагаем, что выпавшее число случайное, но на самом деле это не так, если знать начальное положение кубика, учесть все силы, действующие на него до падения(трением о воздух в принципе можно пренебречь) и поверхность, на которую он упадёт, то можно предсказать, какое там будет число ещё до того, как он упал, но мы этого не знаем и предсказать не можем, поэтому считаем его случайным. В компьютере в качестве такого кубика может служить аппаратный генератор(https://ru.wikipedia.org/wiki/RdRand), шум с звуковой карты, сигнал с вебкамеры, движение мыши, какие-то другие действия пользователя, которые для компьютера являются случайными, а лучше несколько таких источников, смешанных по особым алгоритмам. Для примера можете написать в командной строке линукса cat /dev/random он начнёт выдавать какие-то непонятные символы и рано или поздно они закончатся, если подвигать мышью, на экране может появиться ещё несколько символов.