Rand Implementation

Question

I would like to go through how rand() and srand() functions are implemented and would like to tweak the code to modify it to my requirements. Where can i find the source code of rand() and srand().

Labana

Answer 1

It takes a seed as in input argument, usually like follows:-

double result = srand(time(NULL));

and returns a random number that adheres to the probability and hence expected number of occurrences.

from CodeGuru forums:-

void __cdecl srand (unsigned int seed)
{
    #ifdef _MT
        _getptd()->_holdrand = (unsigned long)seed;
    #else /* _MT */
        holdrand = (long)seed;
    #endif /* _MT */
}

int __cdecl rand (void)
{
   #ifdef _MT
    _ptiddata ptd = _getptd();
    return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) &
    0x7fff );
   #else /* _MT */
    return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
   #endif /* _MT */
}

Hope this helps.

Sop

According to this code holdrand would grow rapidly and soon cause an overflow. holdrand = holdrand * 214013L + 2531011L – Archiepiscopal

About double result = srand(time(NULL));: why on earth do you have that double result? srand doesn't have a return value... – Saffian

can u provide a small explanation of the code or point me to the exact code – Labana

@nikhil: the _MT stuff is code to deal with multithreading (the multithreaded runtime library keeps a separate RNG state for each thread); notice that this is why I avoided to post actual library code: it often contains "elements of distraction" not relevant to the real problem. – Saffian

@nikhil: The actual code is split between several files here: sourceware.org/git/…, and it's quite a mess because it has to take into account a lot of stuff. Again, why do you want to mess with that? You shouldn't and cannot modify it, and the basic algorithm is really simple: if you need to change it, just reimplement it yourself and use your functions instead of the standard library ones. What are you trying to achieve? – Saffian

@nightcracker: sure it overflows, but that's OK because this is an implementation intended for use only on systems that support it. Whoever is putting together the standard libraries (compiler or OS author) just shouldn't use it on systems where signed integer overflow causes a hardware exception... – Falls

By the way, I think the sources in this answer are the ones of Visual C++, not of gcc. – Saffian

The _MT means 'multi threaded'. If the code is intended to be used in a multi-threaded environment it must isolate (thread localize) the seed so the threads dont't contaminate each other (if that matters to you). Older Microsoft code used to make _MT an option. I dont think the _MT option is even available anymore. (~MSVC7) – Cadel

Answer 2

rand and srand are usually implemented as a simple LCG, you can easily write your own (it's few lines of code) without looking for the sources of rand and srand. Notice that, if you need random numbers for "serious" purposes (e.g. cryptography), there are much better RNGs than LCG.

By the way, the C standard itself includes a sample implementation of rand and srand:

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;
}

Saffian

Answer 3

The glibc one (used by gcc) is the simple formula:

x = 1103515245 * x + 12345

wrapping around at 2³², as shown here. You can just set x as the seed then keep calling a function to evaluate that expression (and update the seed).

But you should be aware the linear congruential generators like this are considered adequate but not ideal.

While the only ideal random number generator would be perfectly random, the Mersenne Twister probably comes closer.

Grandpa

s/adequate/mediocre/, I'd say. – Falls