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

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

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

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

rand () не имеет ничего общего со временем. Однако очень часто используется time () для получения «начального числа» для ГПСЧ, так что вы получаете разные «случайные» числа при каждом запуске вашей программы.

Также есть ли в нем тенденции к нечетным или четным числам или что-то вроде этого?

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

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

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

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

Вкратце:

• Вы используете 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 ³² в зависимости от машины, так что при вычислении x _{n + 1} .

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

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

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

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

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

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

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

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