implementation of the random number generator in C/C++

Question

I am a bit confused by the implementation of the random number generator in C, which is also apparently different from that in C++

If I understand correctly, a call to 'srand(seed)' somehow initializes a hidden variable (the seed) that is accessible by 'rand()', which in turn points the function to a pre-generated sequence, like for example this one. Each successive call to 'rand()' advances the sequence (and apparently there are other ways to advance in C++), which also suggests the use of an internal hidden pointer or counter to keep track of the advance.

I have found many discussions on how the algorithms for pseudo-random number generation work and the documentation of the functions rand() and srand(), but haven't been able to find information about these hidden parameters and their behavior, except for the fact that according to this source, they are not thread-safe.

1. Could anybody here please shed some light as to how are these parameters defined and what should be their defined behavior according to the standards, or if their behavior is implementation-defined?

2. Are they expected to be local to the function/method that calls rand() and srand()? If so, is there a way to communicate them to another function/method?

If your answer is specific to either C or C++, please be so kind to point it out. Any information will be much appreciated. Please bear in mind that this question is not about the predictability of data generated by rand() and srand(), but about the requirements, status and functioning of their internal variables as well as their accessibility and scope.

Answer 1

The requirements on rand are:

• Generates pseudo-random numbers.
• Range is 0 to RAND_MAX (minimum of 32767).
• The seed set by srand() determines the sequence of pseudo-random numbers returned.
• It need not be thread-safe or even reentrant, the state can be stored in a static variable.

The standard does not define any way to recover the internal state for reseeding or anything else.

There is no requirement on what PRNG is implemented, so every implementation can have its own, though Linear Congrueantial Generators are a favorite.

A conforming (though arguably useless) implementation is presented in this dilbert strip:

http://dilbert.com/strips/comic/2001-10-25/

Or for those who like XKCD (It's a perfect drop-in for any C or C++ library ;-)):

For completeness, the standard quotes:

7.22.2.1 The rand function

The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.
The rand function is not required to avoid data races with other calls to pseudo-random sequence generation functions. The implementation shall behave as if no library function calls the rand function.
[...]
The value of the RAND_MAX macro shall be at least 32767.

7.22.2.2 The srand function

The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated. If rand is called before any calls to srand have been made, the same sequence shall be generated as when srand is first called with a seed value of 1.
The srand function is not required to avoid data races with other calls to pseudo-random sequence generation functions. The implementation shall behave as if no library function calls the srand function.

C++ includes rand, srand and RAND_MAX without change by reference from the C standard.
There are a few C++ library functions/classes which are explicitly documented to use the C random number generator though.

Answer 2

The following answer is for C; specifically, the 1999 standard.

The C99 standard is very light on actual implementation details for rand & srand. It simply states that the argument to srand is used "as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand."

In practice, the way it usually works is:

• The C library defines an integer variable that rand and srand use to keep track of the PRNG's state.
• srand sets the state variable to the supplied value.
• rand takes the value of the state variable and performs some mathematical magic on it to produce two new integers: one is the pseudo-random number that it returns, and the other becomes the new value for the state variable, thus influencing the next call to rand (assuming srand isn't called before then).

The C standard gives an example of a possible implementation of rand and srand that exhibits this behavior:

static unsigned long int next = 1; 

int rand(void) // RAND_MAX assumed to be 32767 
{ 
    next = next * 1103515245 + 12345; 
    return (unsigned int)(next/65536) % 32768; 
} 

void srand(unsigned int seed) 
{ 
    next = seed; 
}