Xref: utzoo comp.sys.mac:55991 comp.sys.mac.programmer:15799 comp.sys.mac.misc:1094 comp.sys.mac.system:724
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!newstop!sun!prosper
From: vladimir@prosper (Vladimir G. Ivanovic)
Newsgroups: comp.sys.mac,comp.sys.mac.programmer,comp.sys.mac.misc,comp.sys.mac.system
Subject: Re: Random number Generator wanted.
Summary: See CACM v31 #6 and v31 #10 for good, portable random number generators
Keywords: random number generator portable efficient correct
Message-ID: <138515@sun.Eng.Sun.COM>
Date: 7 Jul 90 00:43:48 GMT
References: <8999@goofy.Apple.COM> <9009@goofy.Apple.COM>
Sender: news@sun.Eng.Sun.COM
Reply-To: vladimir@prosper (Vladimir G. Ivanovic)
Followup-To: comp.sys.mac
Organization: sun
Lines: 68
In-reply-to: alexr@ucscb.ucsc.edu (Alexander M. Rosenberg)

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
usablilty 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 2**31 -1 }
	const
	  a = 16807;
	  m = 2147483647;
	  q = 12773;       { 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 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.

Enjoy!

-- Vladimir