Message-Id: <200006091212.IAA10758@delorie.com>
From: "Dieter Buerssner" <buers AT gmx DOT de>
To: djgpp-workers AT delorie DOT com
Date: Fri, 9 Jun 2000 14:20:34 +0200
MIME-Version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Subject: Re: rand() comparison
In-reply-to: <200006082349.TAA30773@envy.delorie.com>
X-mailer: Pegasus Mail for Win32 (v3.12b)
Reply-To: djgpp-workers AT delorie DOT com
Errors-To: nobody AT delorie DOT com
X-Mailing-List: djgpp-workers AT delorie DOT com
X-Unsubscribes-To: listserv AT delorie DOT com
Precedence: bulk

DJ Delorie wrote:

> Could those of you with random number generator testers compare these
> generators?  The first is from DJGPP, and the other two are from
> newlib.

All three are linear congruential generators. The nth random number 
is

x_n = (x_{n-1}*a + b) % c

where in the first case additionally the low bits are discarded.

> #define RAND_MAX 0x7fffffff
> 
> unsigned 
> rand1()
> {
>   static unsigned long long next = 1;
>   next = next * 6364136223846793005LL + 1;
>   return (int)((next >> 21) & RAND_MAX);
> }

I have allready commented on this. It will fail some tests. Using a 
shift of 32 (or 33), will improve this much. But it has the 
weaknesses of all LCGs with a modulus of 2^N (here N is 64).
 
> unsigned
> rand2()
> {
>   long k;
>   static long s = 1;
>   if (s == 0)
>     s = 0x12345987;
>   k = s / 127773;
>   s = 16807 * (s - k * 127773) - 2836 * k;
>   if (s < 0)
>     s += 2147483647;
>   return (int)(s & RAND_MAX);

The mask is not needed here. This RNG should have RAND_MAX defined
as 0x7ffffffe. It will never return 0x7fffffff.

> }

This is an implementation of the Park and Miller minstd. (I think 
it's from the paper cited in the FAQ.) It is equivalent to

x_n = ( x_{n-1} * 16807) % 2147483647,

so it is essentially just two lines of inline assembly.
 
This is about as good, as you can get for a LCG with a 31bit state.
(Note, that 2147483647 = 2^31-1 is a prime). But because of the 
limited period, it will fail some tests.

> unsigned
> rand3()
> {
>   static unsigned int next = 1;
>   return ((next = next * 1103515245 + 12345 ) & RAND_MAX );
> }

This is a very inferior PRNG. It will fail almost all tests. I.e. the 
LSB will just toggle between 0 and 1.

I have test logs of all of those. If you're interested, I can send 
them to you.