Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!snorkelwacker!apple!uokmax!munnari.oz.au!uunet!mcsun!sunic!sics.se!uplog.se!lynx!pem
From: pem@zyx.SE (Per-Erik Martin)
Newsgroups: comp.lang.c
Subject: Re: Random long-number generator
Keywords: random maxint
Message-ID: <1707@lynx.zyx.SE>
Date: 31 Jan 90 20:18:57 GMT
References: <83943@linus.UUCP> <1486@skye.ed.ac.uk> <1540@uniol.UUCP> <1549@mbf.UUCP>
Reply-To: pem@lynx.zyx.SE (Per-Erik Martin)
Organization: ZYX Sweden AB, Stockholm, Sweden
Lines: 58

In article <1549@mbf.UUCP> mark@mbf.UUCP (MHR {who?}) writes:
>
>Nope, no such luck.  You see, what I am usually looking for is a good
>(best would be _fine_!) RNG which uses integer arithmetic only.
>[...]
>So, how about it?
>

The article mentioned previously is "Random number generators: Good ones
are hard to find" by Stephen K. Park and Keith W. Miller, and was published
in Communications of the ACM, October 1988 Volume 31 Number 10.
The generator is based on the function f(z) = 16807z mod 2147483647 which
has a full period.
The article do have an integer arithmetic version of the generator which
could look like this in C:
-----------------------------------------------------------------------------
/* Seed may be any number between 1 and 2147483646 [1, 2^31-2]. */
static unsigned long Seed = 4711;

#define RAND_A      16807L
#define RAND_M 2147483647L
#define RAND_Q     127773L	/* m div a */
#define RAND_R       2836L	/* m mod a */

/* Returns a pseudo random number between 1 and 2147483646 [1, 2^31-2]. */
unsigned long
random()
{
  register long lo, hi, test;

  hi = Seed/RAND_Q;
  lo = Seed - hi*RAND_Q;		/* Seed mod RAND_Q */
  test = RAND_A*lo - RAND_R*hi;
  if (test < 0)
    test += RAND_M;
  return Seed = test;
}
-----------------------------------------------------------------------------
It obviously depends on 32-bit longs. Note that it does not have a full long
period (but it's close enough) and never generates 0. All seeds within the
given interval are equally good, no folklore magic is needed (such as: "at
least five digits with the last one odd").
To check that the implementation of the generator is correct, Seed should
have the value 1043618065 after running this code:

    Seed = 1; i = 10000;
    while (i--) random();

Finally, I should say that I'm no expert at all on random number generators,
I just happened to need a good one and didn't trust home made bit fiddlers.
If you want to know anything about the theories behind the generator above,
you should read the article.

-- 
-------------------------------------------------------------------------------
- Per-Erik Martin, ZYX Sweden AB, Bangardsgatan 13, S-753 20  Uppsala, Sweden -
- Email: pem@zyx.SE                                                           -
-------------------------------------------------------------------------------