Date   : Wed, 28 Sep 1983 12:38:55-PDT (Wed)
From   : decvax!duke!unc!mcnc!ecsvax!dgary@ucb-vax
Subject: Re: Wanted: random number generator written in C

   There seem to be two independent questions here:  What is a good
algorithm for generating random numbers that is independent of hard-
ware, and how do you come up with a reasonably random seed every time
you run?
   Taking the second question first, the problem is fairly trivial if
you have a real time clock (which isn't available in this case,
evidently), or a way to check the keyboard to see if the user has
typed something.  (In the latter case, you ask the user for some
complicated input and generate random numbers until you get a keypress.)
If neither is easily available, you may have a problem!  I suspect a
solution is going to be system-dependent no matter what you do, other
than asking the user for his/her birthday, social security number,
bank balance, SAT score (my old favorite choice of random deviates),
etc..  So I'd suggest you isolate that part of the code.
   Fortunately, random numbers are fairly easy to generate.  The
"standard" way is to take the old seed, multiply by a fixed amount,
add a fixed amount, mod the result (or let it overflow on systems
that aren't traumatized by integer overflow), and that's your next
number and the next seed.  The trick is in generating good values
for the two constants.
   Actually there are THREE constants, counting the multiplier, the
addend, and the thing you mod with (whatever the heck that's called).
Since that's often "automatic" (the silent overflow), you don't hear
it discussed much.  If x is the seed, m the modulus, a the multiplier,
and c the increment, we can use the formula (ax+c) mod m.  M should
be a large number, ideally prime.  If it IS prime, you only need to
choose a and c so that they have no common factors (other than 1),
so they can be made prime.  That guarantees (if memory serves) that
the sequence you get will be at least m long.  It doesn't guarantee
that it will be really "random", and you are probably advised to
experiment with different values for a, c, and m (or even join ACM)
to make sure you get something acceptable.  Knuth (in
Seminumerical Algorithms) waxes eloquent on this subject.
   My own favorite random number generator is incredibly fast and
well-suited to microcomputer and game applications.  It depends on
the silent integer overflow (which all microprocessors provide,
to my knowledge), and can be coded in a few statements in assembler.
   The basic idea is easily visualized by having a circular list
of numbers, at least one of which is odd.  Picture the list written
around the perimeter of the face of a clock.  We disconnect the
mechanism and weld together the hour and minute hands so that they
are a fixed angle apart.  Starting anywhere, we add the contents of
the "box" pointed to by the hour hand to the one pointed to by the
minute hand.  That's our new random number and replaces the one
pointed to by the hour hand.  The we advance the hands one box.
   Only adds and increments are involved, so this is incredibly
speedy.  It also generates very, very long sequences that are hard
to object to on practical grounds (I mean for games...this tech-
nique is probably unadvisable for research work, I've read).  You also
must ensure that the initial set of seeds contains some fairly
widely spaced numbers - the first few dozen (or few thousand) numbers
generated don't look very random if you put small numbers in the
buckets at the outset.
   You need to make sure that you have at least one odd number to
start with (otherwise you can never get one), and the number of boxes
and the "angle between the hands" is important.  Here is the
algorithm in simple form:
   1.  Make array X with elements X[1] to X[5]
   2.  Make integers I and J
   3.  Initialize all X to seed values (at least one odd)
   4.  Initialize I to 2 and J to 5
   5.  Repeat forever:
       Increase X[J] by X[I]
       Output X[J] as the next random number
       Increment I and J, but if either goes over 5, reset it to 1
   The numbers 2 and 5 are "magic".  Others that work (in pairs) are
(1,2), (1,3), (1,4), (2,5), (1,6), (1,7), (3,7), (4,9), (3,10), (2,11),
etc.  In general, the bigger J the longer the sequence.  These numbers
are dependent on doing a mod with a power of 2 (or allowing integer
overflow on a binary machine).
   See Knuth for a long description of all this mess.