nazgul@apollo.UUCP (Kee Hinckley) (10/23/70)
Although it is probably not relevant in this case, I might
mention how the Apple ][ generates it's random number seed for
Applesoft Basic (although it is extensible to the Aztec C that
I use). Quite simply, everytime it checks to see if a character
has been typed at the keyboard (which is everytime it prints a
character, or is waiting for input) it increments a counter. That
counter then can be used as a reasonably random seed for any random
number generator that the user creates.
-keedavidl@tekecs.UUCP (David Levine) (09/27/83)
I am looking for a good public-domain pseudo-random number generator
written entirely in C. Here's the catch: it has to run on Un*x
(Berkeley V7, version 4.1c) and be portable to a CP/M 2.2 system
(Software Toolworks' C compiler version 2.0, with considerable i/o
extensions to emulate stdio) with NO REALTIME CLOCK! I figure the best
way to get pseudo-random numbers is to start with a 'seed' built into
the program, then store the last number generated on disk as a new
seed. Obviously, deleting the file with this seed in it would cause
the program to start over with the original seed, but you can't have
everything. Public-domain source, pointers to non-public-domain stuff
I can study, or just advice would be appreciated.
-- David D. Levine (...decvax!tektronix!tekecs!davidl) [UUCP]
(...tekecs!davidl.tektronix@rand-relay) [ARPA]dgary@ecsvax.UUCP (09/28/83)
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.DHead.es@PARC-MAXC.ARPA (09/30/83)
There is a z80 random number generator described in this months Dr Dobbs Journal written in assembly. It might serve as a model.
Gumby@mit-oz@sri-unix.UUCP (10/05/83)
From: David Vinayak Wallace <Gumby@mit-oz>
Date: Tue, 27-Sep-83 12:23:24 EDT
From: davidl@tekecs.UUCP (David Levine)
I am looking for a good public-domain pseudo-random number generator
written entirely in C.
If you know yor CPM version will run on a Z-80, try using the refresh
register as your random seed. It should be random enough.
Also, BDS-C has a random-number generator included, if you can use that
instead of software toolworks C. The code for the generator may even be
in the public domain.
Hope this helps.
david