Message-ID: <3216D39A.1E83@pobox.oleane.com>
Date: Sun, 18 Aug 1996 10:26:02 +0200
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: djgpp AT delorie DOT com
Subject: Beware of rand()
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Hi,

There seem to be a big problem with function rand() defined in the 
stdlib.h header, so I suggest that any user of nadom number avoid it, 
until it is mended.

Here is the code for the function rand() from stdlib.h
long long
rand(long long next)
{
  next = next * 1103515245L + 12345;
  next = (next<<15) ^ (next >> 27);
  return next;
}

This is the "standard" ANSI linear congruential generator (each number is 
calculated by multiplicating the previous by 110351245 and adding 12345 
(modulo 2**64). There is nothing wrong with this.

Unfortunately, the original generator has been added a "feature", which, 
IMHO, looks a lot like bug.

   next = (next<<15) ^ (next >> 27);

I posted a while a concern on this : did it improve the generator ? 
It seems that the answer is no :

this formula does two copies of next, shift one 15 bits right, the other 
27 left, and xor them together.

Then :

Bits 0-14 are bits 27-41 (xored with 0)
Bits 38-64 are bits 23-50 (also xored with zero)
and the rest are bits 42-64, xored with bits 0-22

You can see that in this 64 bit number, bits 0-14 are equal to bits 
42-56, which makes it a 49 bits number... so long the 2**64 state 
vector...

This also means that two different seeds can give the same rand (this 
would be impossible in a normal congruent generator, such as the one 
obtained by deleting this bit shuffling).

In fact, Josh Rubin has shown that rand() has a period of around 30 
millions (which is very small, a 32 bit generator without the shuffle 
has a period of 4 billions...). It is quite likely that the "shuffling 
trick" has other bad effects on the quality of the generator. 

So, if you need random numbers, redefine rand by copying it in 
src/libc/ansi/stdlib/rand.c and removing the faulty line.
(you can also use random() but rand() is much faster, and no so bad).

BTW, this also accelerates the routine...

Hope this helps,
Francois