From: vladimir@prosper.Eng.Sun.COM (Vladimir G. Ivanovic)
Newsgroups: sci.crypt,alt.security,sci.math
Subject: Re: Random/Pseudo Random Number Generator

The June 1988 (v31 #6) issue of the Communications of the ACM has an article by Pierre L'Ecuyer called, "Efficient and Portable Combined Random Number Generators". The following October (v31 #10), Stephen Park and Keith Miller published "Random Number Generators: Good Ones are Hard to Find."

Both articles are essential reading for anyone interested in random number generation, and this includes naive users. The conclusion of both articles is that horrible random (sic) number generators are used by people who don't know better, while very good ones take less than 20 lines of Pascal! Amoung the horrid generators are some that come with certain systems or are presented in textbooks!

Here are the two proposed random number generators. Even though I have proof read them twice, I made no guarantees whatsoever about the correctness or the usability of the code below.

Here is the Minimal Standard proposed by Park and Miller:

	function Random : real;
	{ Initialize seed with 1..2147483646 }
	{ maxint must be greater than or equal to 2**31 - 1 }
	const
	  a = 16807;
	  m = 2147483647;
	  q = 127773;      { m div a }
	  r = 2836;	   { m mod a }
	var
	  lo, hi, test : integer;
	begin
	  hi := seed div q;
	  lo := seed mod q;
	  test := a * lo - r * hi;
	  if test > 0 then
	     seed := test
	  else
	     seed := test + m;
	 Random := seed / m
       end;

Here is the Portable Combined Generator of L'Ecuyer for 32-bit computers. It has a period of roughly 8.12544 x 10^12.

	Function Uniform : real;
	{ Initialize s1 to 1..2147483562; s2 to 1..2147483398 }
	  var
	    Z, k : integer;
	  begin
	    k  := s1 div 53668;
	    s1 := 40014 * (s1 - k * 53668) - k * 12211;
	    if s1 < 0 then s1 := s1 + 2147483563;
	    
	    k  := s2 div 52774;
	    s2 := 40692 * (s2 - k * 52774) - k * 3791;
	    if s2 < 0 then s2 := s2 + 2147483399;

	    Z := s1 - s2;
	    if Z < 1 then Z := Z + 2147483562;

	    Uniform := Z * 4.656613e-10;
	  end;

All are urged to read both articles for a much better presentation. And you don't have to be a mathematician to understand them: very little of either article is not accessible to a competent programmer.

A recent article [P. L'Ecuyer, F. Blouin & R. Couture, "A Search for Good Multiple Recursive Random Number Generators", ACM Transactions on Modeling and Computer Simulations, Vol 3, No. 2, April 1993] suggests that certain multiple recursive generators (MRGs) of the form

       x  = (a x   + ... + a x   ) mod m
        n     1 n-1         k n-k

have good properties, longer periods and are easy to implement than the more common multiplicative linear congruential generators (MLCGs) of the form

       x  = ax    mod m
        n     n-1

The authors identify a good MRG, supply parameters and provide sample implementations in C and Pascal. I implemented this MRG and obtained some results.

I've included below the code I used, information about the system on which I compiled and ran the code, the exact compilation and linking commands used, and finally, the results of running the included code.

The code

...has been moved here (C-Version only).

uname -a ==>
SunOS prosper 5.3 Generic_Patch sun4m sparc

cc -# -V -o TestRandomC TestRandom.c ==>

cc: SC3.0.1 26 May 1994
rest of compiler-output deleted

pc -v -V -o TestRandomP TestRandom.p ==>

pc: SC3.0.1 26 May 1994
rest of compiler-output deleted

rm TestRandom.o

TestRandomC
    0:  5.024326127022505e-02
    1:  8.260946767404675e-02
    2:  2.123264316469431e-02
    3:  6.926658791489899e-01
    4:  2.076155943796039e-01
    5:  4.327449947595596e-02
    6:  2.204052871093154e-02
    7:  1.288446951657534e-01
    8:  4.859915426932275e-01
    9:  5.721384193748236e-02
   10:  7.996825082227588e-01

TestRandomP
    0:  5.024326127022504807e-02
    1:  8.260946767404675484e-02
    2:  2.123264316469430923e-02
    3:  6.926658791489899158e-01
    4:  2.076155943796038628e-01
    5:  4.327449947595596313e-02
    6:  2.204052871093153954e-02
    7:  1.288446951657533646e-01
    8:  4.859915426932275295e-01
    9:  5.721384193748235703e-02
   10:  7.996825082227587700e-01