From: Kbwms AT aol DOT com
Message-ID: <619145f5.36408b1e@aol.com>
Date: Wed, 4 Nov 1998 12:13:02 EST
To: dj AT delorie DOT com
Cc: djgpp-workers AT delorie DOT com
Mime-Version: 1.0
Subject: New Multiplier for Function rand()
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7bit
X-Mailer: AOL 3.0 16-bit for Windows sub 38
Reply-To: djgpp-workers AT delorie DOT com

Dear DJ Delorie,

As previously reported, the multiplier used in rand.c fails in the
third dimension the spectral test for congruential random number
generators.  A demonstration of this fact is appended.

A better multiplier is contained in the patch listed below.  This
multiplier was taken from Knuth, Donald .E., *The Art of Conputer
Programming*, Vol. 2, Seminumerical Algorithms, Third Edition,
Addison-Wesley (1998), page 106, Table 1, line 26.  This multiplier
passes the spectral test in dimensions 2 through 8 as shown in the
appended spectral test run.


*** rand.c~     Sun Sep  8 23:49:42 1996
--- rand.c      Wed Nov  4 10:06:56 1998
***************
*** 7,13 ****
  int
  rand(void)
  {
!   next = next * 0x5deece66dLL + 11;
    return (int)((next >> 16) & RAND_MAX);
  }

--- 7,13 ----
  int
  rand(void)
  {
!   next = next * 6364136223846793005 + 1;
    return (int)((next >> 16) & RAND_MAX);
  }


K.B. Williams
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
# DJ Delorie Generator for GNU rand()
                     1                     Number of Multipliers
                     25214903917           Multiplier
                     18446744073709551616  Modulus
                     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

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

# C.E. Haynes - taken from Knuth, Art of Computer Programming, pp 106-107
                     1                     Number of Multipliers
                     6364136223846793005   Multiplier
                     18446744073709551616  Modulus
                     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