jeff@ISI-VAXA.ARPA (Jeffery A. Cavallaro) (10/02/85)
(I have never really worked on an application that required the use of a
random number generator. In addition, I know little about random number
generation theory. Thus, the following questions may seem a little
elementary to some out there...)
Upon playing with (s)random(3), I noticed that the same seed produces the
same sequence. I guess this is what is meant by "pseudo-random". The
following points struck me:
1. What good is a random number generator when you have to generate a
random seed to begin with.
Now, I realize that the seed generation is usually off of system time, or
PIDs, or some such constantly increasing number, but this seems to lead
to a dilemma:
2. Numbers such as PIDs repeat relatively frequently, especially on machines
that tend to reboot. In the case of a "server-type" process, it may
not vary at all.
3. Numbers such as system-time, which theoretically NEVER repeat may
never regenerate the same sequence.
Now, if one wants to try and simulate reality, such as the shuffling of
a card deck, what is one to do. PIDs will repeat to often, whereas system
time may not repeat at all. Not repeating at all may or may not be
appropriate for various physical simulations.
Are (1), (2), and (3) wrong, am I totally out to lunch, do I have a point,
are there any good references???
Jeffta2@edison.UUCP (tom allebrandi) (10/05/85)
> > (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 ...............
mather@uicsl.UUCP (10/07/85)
A pretty good reference that contains many ideas on the theory of computer generated random sequences is: "Computer approaches to Mathematical Problems" -by Nievergelt, Farrar, & Reingold Pretice Hall series in Automatic Computation Chapter 4 is entitled: "Random Processes on Deterministic Computers" You may find this helpful, if not fun to read. Other chapters are on game-playing, decision making, the traveling salesman problem (where to sleep when the farmer has no daughter), backtracking, etc. ---- b.c.mather Software Surgeon uiucdcs!uicsl!mather