From: Kbwms AT aol DOT com
Message-ID: <9fc72b10.3614ebaf@aol.com>
Date: Fri, 2 Oct 1998 11:05:19 EDT
To: eliz AT is DOT elta DOT co DOT il, dj AT delorie DOT com
Cc: djgpp-workers AT delorie DOT com
Mime-Version: 1.0
Subject: Re: Proposed New Random
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7bit
X-Mailer: AOL 3.0 16-bit for Windows sub 38

Dear Eli Zaretskii,

On 10-01-98 at 15:57:30 EST you wrote:
>
> On Thu, 1 Oct 1998, DJ Delorie wrote:
>
> > > And second, one of the most valuable features of `random' is that all
> > > its bits, inluding the LSB's, are random, so you could get a random
> > > bit with "random() % 2".  Does your algorithm have this feature?
> >
> > Actually, I think rand() has this property at the moment, because it
> > uses a 64-bit seed and extracts the middle 32-bits for the return
> > value.
>
> It would be interesting to run some tests on it from Knuth's v.3.  Any
> takers?
>

Been there, done that.  For 32-bit random number generators, I wrote the
following tests:

    collision
    frequency
    maximum-of-t
    permutation
    run
    serial
    serial correlation

And the spectral test for linear congruential generators using multipliers
up to 64 bits, such as DJGPP's 'rand.'

Descriptions of the tests can be found in Knuth, Vol. 2, "Seminumerical
Algorithms," pp 59-71 and 89-105 (The Spectral Test).

Yesterday, I ran the collision test in two dimensions on both 'rand' and
'random.'  The results for 'random' indicate that this generator produces
variates that are random in two dimensions.  For 10 collision tests, each
test consisting of 50 individual collision tests, the Kolmogorov-Smirnov
probabilities were:

     K-S               K-S
  Statistic        Probability
  ---------        -----------
0.0697959896     0.046195095361434
0.0897959896     0.218454918034336
0.1009707242     0.349312322389802
0.1097959896     0.453741235577377
0.1113396029     0.471490118966196
0.1127025048     0.486972082264050
0.1214023802     0.580667333236228
0.1221745996     0.588496954355624
0.1378254004     0.727616272736865
0.2067544851     0.976209479701211


On the other hand, function 'rand' produced the following K-S
probabilities:

     K-S               K-S
  Statistic        Probability
  ---------        -----------
0.3954793555     0.999999857157875
0.4127025048     0.999999969986998
0.4152982702     0.999999976497470
0.4254298932     0.999999991189763
0.4527025048     0.999999999526494
0.4608517265     0.999999999826248
0.4713396029     0.999999999960549
0.4727025048     0.999999999968357
0.5054298932     1.000000000000000
0.5131576122     1.000000000000000


This indicates behavior that is decidedly non-random.  The tests of
'rand' were conducted on the lower bits of each number generated.
Despite the fact that 'rand' returns the "middle 32-bits," Knuth
points out on pages 12 and 14 that even these bits will suffer non-
random behavior.  It is my experience that the upper bits will fare
far better.

I will run tests on the upper bits if anyone is interested.



K.B. Williams