Understanding the algorithm of Visual C++'s rand() function

Question

In C/C++, rand() and srand() are usually used by us when we want to get a random integer. But when I tried to rewrite it myself, I found it difficult to understand the algorithm. The function is very easily written in only a few lines, but the formula is misunderstanding.

The main formula:

ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L;

The original code involved:

void __cdecl srand (unsigned int seed)
{
    _getptd()->_holdrand = (unsigned long)seed;
}

int __cdecl rand (void)
{
    _ptiddata ptd = _getptd();
    return ( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff );
}

Answer 1

It's just modular arithmetic. You're multiplying and adding to a number which is taken modulo 2^32 (for example), and returning the upper 16 bit as your "random" number. Because you're multiplying and adding numbers which are coprime to the modulus, this creates sort of uniformly distributed numbers.

The careful choice of the two numbers is very important. For example, if you had used "* 4" and "+ 8", you would probably not experience a lot of randomness.

This scheme is called linear congruential.

Answer 2

That pseudorandom number generator is a Linear Congruential Generator.

Answer 3

You can find an explanation of the Linear Congruential Generator (LCG) and other similar families or pseudo random generators, and about the selection of these specific constants in an excellent article published this month (7-2011) in Dr. Dobb's Journal (DDJ): Fast, High-Quality, Parallel Random-Number Generators: Comparing Implementations.

I think you'll need to register at DDJ's website (free) to read the first part of this article (link), but if you're into C++ and mathematics you should do it anyway...