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

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:

开发者_StackOverflowptd->_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 );
}

---

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.

---

That pseudorandom number generator is a Linear Congruential Generator.

---

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

---

Prior to calling rand, since the man page for srand indicates that "If no seed value is provided, the rand() function is automatically seeded with a value of 1", then a better approach to invoking rand is to first invoke srand which will "set its argument as the seed for a new sequence of pseudo-random integers to be returned by rand()".

As an example, consider the following awk, nawk, gawk code which is used in a bash shell script to create a new (random) mac address - i.e. .genmacaddr referenced in code snippet:

enter code here
BEGIN {
     n0 = "00"
     srand()
     n1 = sprintf("%02x", int(255 * rand()))
     n2 = sprintf("%02x", int(255 * rand()))
     n3 = sprintf("%02x", int(255 * rand()))
     n4 = sprintf("%02x", int(255 * rand()))
     n5 = sprintf("%02x", int(255 * rand()))
     print n0":"n1":"n2":"n3":"n4":"n5
}

where the code snippet in the bash shell script is:

enter code here
ifconfig eth0 down
newmacaddr=`nawk -f .genmacaddr -`
ifconfig eth0 hw ether $newmacaddr
ifconfig eth0 up

If I am not mistaken, the seed value for srand is derived from the system clock.

I hope this helps you to understand an approach to your coding solution that will work.

---

As has been said it's a linear congruential, (you can look that up if you want in depth commentary on how these generate pseudo-random values)

the seed is stored in _getptd()->_holdrand (hereafter called holdrand)

This code "works" by doing the normal multiply and add step but then overflowing holdrand to get the implied "modulus" 0x100000000.

I mention this because it's not immediately obvious, and generally not considered good style.

Technically overflowing an integer variable isnvokes the undefined behaviour, but on most platforms it's quite predictable so Microsoft's engineers are ignoring that issue.