Как работает rand()? Есть ли у него определенные тенденции? Есть ли что-то лучше использовать?

Question

Я читал, что это как-то связано со временем, в том числе и с помощью time.h, поэтому я предположил, что это так, но как именно это работает? Кроме того, есть ли у него склонность к нечетным или четным числам или что-то в этом роде? И, наконец, есть что-то с лучшим распространением в стандартной библиотеке C или в среде Foundation?

Answer 1

Кратко:

• Ты используешь time.h чтобы получить семя, которое является начальным случайным числом. Затем C выполняет несколько операций с этим номером, чтобы получить следующее случайное число, затем выполняет операции с этим номером, чтобы получить следующее, затем... вы получаете изображение.

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

• C не имеет другого встроенного генератора случайных чисел. Если вам нужен действительно сложный пакет, в Интернете доступно множество пакетов, но алгоритм Mersenne Twister, вероятно, является наиболее популярным выбором.

Теперь, если вы заинтересованы в причинах, почему вышеизложенное верно, вот ужасные подробности о том, как rand() работает:

rand() это то, что называется " линейный конгруэнтный генератор ". Это означает, что он использует уравнение вида:

x _{n + 1} = (* a **** x _n + *** b *) mod m

где x _n - это n- ^е случайное число, а a и b - некоторые заранее определенные целые числа. Арифметика выполняется по модулю m, причем m обычно 2 ^{32 в} зависимости от станка, так что в вычислении x _{n + 1} сохраняются только самые младшие 32 бита.

Таким образом, в английском языке идея такова: чтобы получить следующее случайное число, умножьте последнее случайное число на что-то, добавьте к нему число, а затем возьмите последние несколько цифр.

Несколько ограничений быстро становятся очевидными:

• Во-первых, вам нужно стартовое случайное число. Это "семя" вашего генератора случайных чисел, и именно здесь вы слышали time.h использовался. Так как мы хотим получить действительно случайное число, обычной практикой является спросить систему, который час (в целочисленной форме), и использовать это в качестве первого "случайного числа". Кроме того, это объясняет, почему использование одного и того же начального числа дважды всегда будет давать одинаковую последовательность случайных чисел. Это звучит плохо, но на самом деле полезно, так как отладка намного проще, когда вы управляете входами в вашу программу

• Во-вторых, a и b нужно выбирать очень, очень тщательно, иначе вы получите некоторые катастрофические результаты. К счастью, уравнение для линейного конгруэнтного генератора достаточно просто, что математика была разработана с некоторыми подробностями. Оказывается, что выбор a, который удовлетворяет *a***mod8 = 5 вместе с *** b * = 1, гарантирует, что все m целых чисел одинаково вероятны, независимо от выбора затравки. Вы также хотите получить значение a, которое действительно велико, так что каждый раз, когда вы умножаете его на x _n, вы запускаете модуль по модулю и отсекаете много цифр, иначе много чисел подряд просто будут кратны друг другу. В результате два общих значения (например) 1566083941 и 1812433253 согласно Кнуту. Библиотека GNU C использует a = 1103515245 и b = 12345. Список значений для многих реализаций доступен на странице Википедии для LCG.

• В-третьих, линейный конгруэнтный генератор фактически повторяется из-за этого по модулю. Это может быть довольно умопомрачительной математикой, но результат всего этого, к счастью, очень прост: последовательность будет повторяться после того, как будет сгенерировано m чисел. В большинстве случаев это означает, что ваш генератор случайных чисел будет повторяться каждые 2 ³² цикла. Это звучит как много, но это действительно не для многих приложений. Если вы выполняете серьезную численную работу с симуляциями Монте-Карло, это число безнадежно неадекватно.

• Четвертая, гораздо менее очевидная проблема заключается в том, что числа на самом деле не случайны. У них забавная связь. Если вы возьмете три последовательных целых числа (x, y, z) из LCG с некоторым значением a и m, эти три точки всегда будут попадать в решетку точек, созданных всеми линейными комбинациями трех точек (1, a, а ²), (0, м, 0), (0, 0, м). Это известно как теорема Марсальи, и если вы ее не понимаете, ничего страшного. Все это означает следующее: триплеты случайных чисел из LCG покажут корреляции на некотором глубоком, глубоком уровне. Обычно это слишком глубоко для вас или меня, чтобы заметить, но это там. Можно даже восстановить первое число в "случайной" последовательности из трех чисел, если вам дают второе и третье! Это плохо для криптографии.

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

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

Answer 2

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

Числа должны быть распределены так, чтобы они выглядели несколько случайными, поэтому, например, нечетные и четные числа должны возвращаться примерно с одинаковой частотой. Фактическая реализация генератора случайных чисел не указана, поэтому фактическое поведение зависит от реализации.

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

Answer 3

Как работает rand()?

http://en.wikipedia.org/wiki/Pseudorandom_number_generator

Я читал, что это как-то связано со временем, также вы получаете от включения time.h

rand() не имеет ничего общего со временем. Тем не менее, это очень распространено в использовании time() чтобы получить "начальное число" для PRNG, чтобы вы получали разные "случайные" числа при каждом запуске вашей программы.

Кроме того, есть ли у него склонность к нечетным или четным числам или что-то в этом роде?

Зависит от используемого метода. Есть одна популярная реализация rand() который чередуется между нечетными и четными числами. Так что избегайте написания кода вроде rand() % 2 это зависит от того, является ли младший бит случайным.