Как функция rand()/srand() реализована в C

Question

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

Я знаю, как это реализовать. Однако я хотел бы понять, как rand ведет себя внутренне и почему необходимо инициализировать начальное значение для функции rand.

В качестве альтернативы - как функция rand использует начальное значение для генерации случайных чисел?

Answer 1

Точные детали реализации зависят от разработчиков. Но реализация GNU (glibc) реализует rand() следующим образом: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.15

Комментарий объясняет это довольно хорошо.

/* If we are using the trivial TYPE_0 R.N.G., just do the old linear
    congruential bit.  Otherwise, we do our fancy trinomial stuff,
    which is the same in all the other cases due to all the global
    variables that have been set up.  The basic operation is to add
    the number at the rear pointer into the one at the front
    pointer.  Then both pointers are advanced to the next location
    cyclically in the table.  The value returned is the sum generated, 
    reduced to 31 bits by throwing away the "least random" low bit.    
    Note: The code takes advantage of the fact that both the front and 
    rear pointers can't wrap on the same call by not testing the rear  
    pointer if the front one has wrapped.  Returns a 31-bit random number. */

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

Есть только генераторы псевдослучайных чисел, которые генерируют потоки чисел, которые выглядят случайными, но они все еще являются результатами детерминированных вычислений. Вот почему вам нужно начальное значение: каждое начальное число приводит к различной последовательности чисел. Когда вы используете одно и то же начальное число, вы получаете одинаковую последовательность псевдослучайных чисел.

Можно использовать поведение, при котором ГСЧ всегда возвращает одну и ту же последовательность при получении одного и того же начального числа: например, классическая космическая симуляция Elite смогла хранить огромную вселенную с сотнями планет в одном целом числе. Как он это сделал? Вся вселенная была сгенерирована случайным образом. Все данные, которые требовались для воссоздания юниверса, были начальным значением, которое всегда приводило к созданию точно такой же юниверса.

Answer 2

Смотрите Википедию для более подробного объяснения.

Линейный конгруэнтный генератор (LCG) представляет собой один из старейших и наиболее известных алгоритмов генератора псевдослучайных чисел.[1] Теория, лежащая в их основе, проста для понимания, и они легко осуществимы и быстры.

Генератор определяется рекуррентным соотношением:

X_ {n + 1} = (a * X_n + c) mod m

Answer 3

Наиболее rand реализации представляют собой LCG, который использует базовую математику для выполнения микширования. Как и большинство PRNG, требуется, чтобы рандомизированное начальное число частично удаляло его детерминированную природу (это и хорошо, и плохо, зависит от того, для чего он предназначен), созданное с использованием фиксированных и предсказуемых математических функций.

Answer 4

Если вы заинтересованы в том, какие алгоритмы используются для реализации rand() на практике, какие общие алгоритмы используются для C rand()? может быть интересным. Реализация glibc, а также несколько ссылок на статьи, объясняющие другие алгоритмы.

Что касается вопроса о том, почему вы должны установить начальное число, начальное число - это то, что мешает генератору случайных чисел каждый раз генерировать одну и ту же последовательность чисел. Так как нет настоящих генераторов случайных чисел, если вы звоните srand(constant) а также rand() 5 раз, 5 "случайных" чисел, которые вы получите, всегда будут одинаковыми. Однако, если вы начнете со значения, которое будет отличаться каждый раз rand() используется (по умолчанию это время в секундах с эпохи Unix, я думаю), тогда у вас не будет этой проблемы.