How is the rand()/srand() function implemented in

Question

Possible Duplicate:
How does rand() work? Does it have certain tendencies? Is there something better to use?

I know how to implement it. However, I would like to understand how the rand behaves internally and why is it necessary to initialise a 'seed' value for the rand function.

Alternately put — how does the rand function use the seed value to generate random numbers?

Answer 1

See Wikipedia for a more detailed explanation.

A Linear Congruential Generator (LCG) represents one of the oldest and best-known pseudorandom number generator algorithms.[1] The theory behind them is easy to understand, and they are easily implemented and fast.

The generator is defined by the recurrence relation:

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

Answer 2

If you're interested in what algorithms are used to implement rand() in practice, What common algorithms are used for C's rand()? might be of interest. glibc's implementation is there as well as a few links to articles explaining other algorithms.

As for the question of why you must set a seed, the seed is what prevents the random number generator from producing the same sequence of numbers every time. Since there are no true random number generators, if you call srand(constant) and rand() 5 times, the 5 "random" numbers you get back will always be the same. However, if you seed with a value that will be different each time rand() is used (the default is the time in seconds since the Unix epoch I think), then you won't have this issue.

Answer 3

The exact implementation details are up to the implementors. But the GNU implementation (glibc) implements rand() like that: http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;hb=glibc-2.15#l361

The comment explains it pretty well.

/* 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. */

Regarding your question why you always need a seed value: There are no truly random numbers in computer science. Computers are (in computation theory) completely deterministic machines. They can't perform any operations with an outcome which is up to chance.

There are only pseudorandom number generators which generate streams of numbers which look random, but they are still the results of deterministic calculations. That's why you need a seed value: each seed results in a different sequence of numbers. When you use the same seed, you get the same sequence of pseudorandom numbers.

The behavior that a RNG always returns the same sequence when getting the same seed can be exploited: The classic space simulation Elite, for example, was able to store a huge universe with hundreds of planets in a single integer. How did it do that? The whole universe was randomly-generated. All data which was required to recreate the universe was the seed value, which always resulted in the exact same universe being generated.

Answer 4

Most rand implementations are an LCG, which uses basic math to perform the mixing. Like most PRNG's, it requires the randomized seed to partially remove its deterministic nature (this is both good and bad, depends what its intended use is) created by using fixed & predictable mathematical functions.