From: Kbwms <Kbwms AT aol DOT com>
Message-ID: <8e5722f0.35435f96@aol.com>
Date: Sun, 26 Apr 1998 12:23:48 EDT
To: djgpp AT delorie DOT com
Mime-Version: 1.0
Subject: Problem with Function rand()
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7bit
Precedence: bulk

While completing an article entitled _Quick and Portable Random
Number Generators_ with Gerald P. Dwyer (Clemson University), I
ran tests on random number generators in several C libraries,
including Microsoft, Borland, and GNU.  The 16-bit versions in
the Microsoft and Borland libraries seem to behave well enough
but their cycle-length is far too short for serious work.

The availability of 32-bit output from a Lehmer generator led
me to test the version of rand() in the GNU C library.  When
possible, the first test to be conducted is the spectral test.
(See Knuth, The Art of Computer Programming, Vol 2, 1981, pp.
89-110.)

The code reveals that registers of type long long int are used
to calculate new values (mod 2^32) of output from a 64-bit linear
congruential generator (mod 2^64).  Apparently, this generator
fails the third dimensional test as shown here:


# Generator for GNU rand()
    1                     Number of Multipliers
    25214903917           Multiplier
    18446744073709551616  Modulus 2^64
    8                     Maximum Dimension of Test

Dimension    Accuracy     Ratio of        Number      Figure of
                       minimum possible   of bits       merit
                         distance to                   [Knuth]
                       actual distance
    2 3277608498.04455      .710170          31.6         1.83
    3     743138.35377      .250568          19.5          .09
    4      59147.43202      .758924          15.9         3.27
    5       6202.61783      .706451          12.6         2.62
    6       1436.93424      .685008          10.5         2.47
    7        548.54170      .720979           9.1         3.83
    8        211.84428      .585143           7.7          .89


One of Knuth's guidelines is that the "Figure of merit" should be
.1 or larger.

A better choice of multiplier for modulus 2^64 is one recommended by
Knuth.  The figures of merit are all well above 1 which means that
the multiplier "passes with flying colors" (Knuth op cit, page 102).

# C.E. Haynes - taken from Knuth, Art of Computer Programming, pp 102-104
    1                     Number of Multipliers
    6364136223846793005   Multiplier
    18446744073709551616  Modulus 2^64
    8                     Maximum Dimension of Test

Dimension    Accuracy     Ratio of        Number      Figure of
                       minimum possible   of bits       merit
                         distance to                   [Knuth]
                       actual distance
    2 2968276296.88587      .643146          31.5         1.50
    3    2529487.06393      .852879          21.3         3.68
    4      64129.83912      .822854          16.0         4.52
    5       6757.42821      .769642          12.7         4.02
    6       1358.81125      .647765          10.4         1.76
    7        549.97273      .722860           9.1         3.90
    8        230.77262      .637425           7.9         1.77

The numbers in the last two columns agree with those in Knuth at
line 30 on page 103.  The numbers in column two above are the square
roots of those shown in the table on page 102, line 30.


K.B. Williams