From: buers AT gmx DOT de (Dieter Buerssner)
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Uptime and entropy in DOS
Date: 15 Feb 2000 16:10:31 GMT
Lines: 58
Message-ID: <88btpm$128uk$3@fu-berlin.de>
References: <Pine DOT SUN DOT 3 DOT 91 DOT 1000215095332 DOT 23996N-100000 AT is>
NNTP-Posting-Host: af680.pppool.de (213.6.246.128)
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: fu-berlin.de 950631031 1123284 213.6.246.128 (16 [17104])
X-Posting-Agent: Hamster/1.3.8.0
User-Agent: Xnews/2.11.08
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

djgpp AT delorie DOT com (Eli Zaretskii) wrote in 
<Pine DOT SUN DOT 3 DOT 91 DOT 1000215095332 DOT 23996N-100000 AT is>:

>
>On Mon, 14 Feb 2000, Campbell, Rolf [SKY:1U32:EXCH] wrote:
>
>> > BSD random() seems to use the Apple RNG
>> >   x = (x * 16807) % ((2 << 31) - 1);
>> > to play with the seed.
>> 
>>     I believe that algorithm is not very good at making random
>>     numbers.
>
>If this is used only to randomize the seed, then it is okay.
>
>But I don't see the above calculation anywhere in the sources of
>`random.c', at least as it appears in DJGPP v2.03.

Yes, usually BSD random() won't use a calculation, as above, to
produce it random numbers.

If the random() is used in default mode (rand_type = 3), random()
seems to be a lagged Fibonacci RNG.
This means the nth random number

r[n] = r[n-r] op r[n-s];

with constants r and s (31,3) and op = +. (The array r[] is
implemented as a cyclic buffer, only the last max(r,s) elements
need to be stored.)
In general op can be ^,+,-,* (on odd numbers). Knuth suggests
r=55, s=24 and op = -; 
Lagged Fibonacci generators have a very long period.
There exist lists of suitable constants r and s, that guarantee
a maximal period. I have not found
(31,3) on these lists, rather I have seen (31,13). To me it seems,
that this really was not intended. I tested BSD random with the
diehard tests of Marsaglia, as well as with some own tests
for randomness. In general, it does quite well. But there is one
simple test, the birthday spacings test, which fails big time
with random(), and almost all lagged Fibonacci RNGs (* on odd
numbers is the exception).

So, if you really need a good RNG, I would suggest to not
use random(). You might want to do a net search on Marsaglia
and Mersenne Twister.

When rand_type = 0, BSD random produces very bad random numbers
with an alternating least significant bit. Then it uses a
linear congruential generator,
  r[n] = (r[n-1]*a + b) % m; /* a, b and m are suitable constants */
simular to the code shown by Rolf, but IMHO even worse, because
m is a power of two.

Regards,
Dieter