RANDOM NUMBER GENERATORS

[tom allebrandi]

> 
> (I have never really worked on an application that required the use of a
> random number generator.

I have often used them to test communication systems - ie generate
"random" message sequences to test the receiving message parser...
The gaming and simulation theory people make use of the properties of
both "real random" and "pseudo random" numbers.

> 
> 1.  What good is a random number generator when you have to generate a
>     random seed to begin with.
> 

Question to the net: Has not someone proven that a deterministic machine
cannot exhibit random behavior? (unless of course it is one of our 11/785's
(-: ) If so; then some form of external input must be required to kick off
the "random" sequence.

> 3.  Numbers such as system-time, which theoretically NEVER repeat may
>     never regenerate the same sequence.
> 

Not necessarily true. Most people do not use the raw numbers that come
from a random number generator; but map them into something else. Here,
one counts on the fact that the raw numbers are uniformly distributed;
resulting in the probabilty of any mapped output occurring being based
solely on the mapping function. For example if my random number generator
gives numbers on [0.0..1.0); the mapping of trunc(random(n)*52.0) gives me
uniformly distributed results in the set [0..51] - very useful for
card simulations.

While I took the longwinded way to get here; note a couple of properties:

a) a mapping function - such as the one above - is usually a many to one
   mapping. Because of this, we can have selected input->map->output
   sequences that are the same in output but different in input. (selection
   being based on the size of the sequence - if you chose 2^31 as your
   sequence size you won't see it repeat very often)

b) many random number generators are based on the multiplicitive congruence
   algorithm described in Knuth Vol 2. This algorithm generates
   pseudo random sequences of integers; not real numbers. To get real
   numbers; people like DEC in VMS use a 32 bit mc algorithm to generate
   "random integers" then discard the high 8 bits and convert to real. Since
   the discard is again a many to one mapping function; we can expect 
   that a sequence of random numbers can occur more than once - coming from
   different seeds.

> 
> Are (1), (2), and (3) wrong, am I totally out to lunch, do I have a point,
> are there any good references???
> 

I would probably check any good simulation/gaming/queueing(?) theory text
for uses of "randomness". Knuth Vol 2 "Seminumerical Algorithms" spends
over 150 pages on random numbers; their properties and their generation.

As an aside; I have VAX assembler and 8086 assembler sources of implementations
of multiplicitive congruence. The 8086 version is in Microsoft V3 assembly
and requires an 8087. (it will work on the PC with the 8087 emulator) Send
me mail if you would like to have either...

-- 
...............
tom allebrandi 2, general electric automation controls operation
UUCP: ...decvax!mcnc!ncsu!uvacs!edison!ta2
box 8106, charlottesville, va, 22906
(804) 978-5566
...............