DPRG
DPRG List  



DPRG: "Random" Numbers

Subject: DPRG: "Random" Numbers
From: Eric B. Olsen robojoc at worldnet.att.net
Date: Mon Jan 12 23:15:20 CST 1998

Hi all,

Regarding random number generators, I have taken someone's advice out
there and looked in to my Numerical Recipes in C book!  The write-up
turned out to be very interesting ... The truth about many RNG's out
there is that they are not very good at all, and while even bad random
number generators may work for given robotic application, why use them
if there's something better?

In my gaming experience, I 've come across several different forms of
algorithms; two of the most dominent are "linear congruential type", and
"shift register feedback" type.  I've chosen to list the former type as
this is documented in the Numerical Recipes book and has test references
available.

The routine is documented as a quick and fast method that yields
acceptable results.  The book also instructs that 32 bit RNG's are
highly preferred over other shorter sequence algorithms.  The routine
is:



unsigned long idum;

idum = 1664525L * idum + 1013904223L;


 That's it!  Everytime you need a number, execute the recurrence
equation (remember, don't trash 'idum', it'll be needed exactly as is in
the next call).  The seed value is any number that you initially start
idum with.

If you need a floating point number, a (somewhat dirty) trick that is
documented in the book as follows: (which is apparently specific to IEEE
format floating point numbers)


unsigned long idum, itemp;
float rand;

static unsigned long jflone = 0x3f800000;
static unsigned long jflmsk = 0x007fffff;

idum  = 1664525L * idum + 1013904223L;
itemp = jflone | (jflmsk & idum);
rand = (*(float *)&temp)-1.0;


Of course, the down side to these routines is the need for 32 bit
integer operations, however, this is required if the RNG is going to
yeild minimally acceptable results in terms of sequence length (repeat
period).

The book also mentions that to generate a range of random numbers, it is
best to use the most significant digits of the number as opposed to the
least significant bits, thus, when requiring a random number between 1
and 10, you should use something like:

j = 1 + (int)(10.0 * rand( ) / (RAND_MAX + 1.0))

of course, notice that this means you have floating point available.

The book says that forms like:

j = 1 + (rand( ) % 10)

are not recommended as they use lower order bits...although I'll have to
admit I've used these when the generators are "free-running".

You'll have to take the above statements and place them into a function
call, remembering that "idum" is a global variable.

In electronic gaming devices, another trick is used to keep the
randomness of the generator very high, that is, keep the RNG
"free-running" in the background, perhaps in a timer interrupt if
possible.  (Free running means the generator keeps pulling numbers
regardless of whether they are needed or not!)  This means that you'll
have to structure a routine to retreive a valid state of the RNG, which
can be a bit tricky  (disable interrupts!!) ... however, the results are
amazing since your gnerator generates a "random" number, not just
"psuedo-random numbers"!   i.e. the real world is influencing when the
numbers are pulled from a generator that is constantly going!

Hope some of this stuff's been useful!


Eric Olsen

- --

"Time will tell if the human race can handle the responsibility of it's
own evolution"

Spectronix, Inc.
Fax:
Email:  robojoc at worldnet.att.net
Web-Site:
Henderson, NV

------------------------------

More information about the DPRG mailing list