martens@ketch.cis.ohio-state.edu (Jeff Martens) (09/13/89)
In article <1989Sep13.032352.10321@agate.berkeley.edu> mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer) writes:
:As a general rule, serious applications should never use the random
:number generator provided with a language. You should either use one
:from a "known-good" library (i.e. - IMSL, if there's a random number
:generator in it), or roll your own. Rolling your own can be done in an
:afternoon, including chasing down and reading the references. Knuth's
:"The Art of Computer Programming" vol. 2 - "Seminumerical Algorithms"
:- is the canonical reference, and has lots of theory plus various
:algorithms for testing random-number generators. R. G. Dromey's "How
:to Solve It By Computer" (part of the Prentice-Hall International
:Series in CS, edited by C.A.R. Hoare) extracts the important part for
:the do-it-yourselfer into a few pages that describe the best algorithm
:from Knuth, what the parameters are, and how to choose them.
Another good (and easy to find) reference for random number generation
is Park and Miller, "Random Number Generators: Good Ones are Hard to
Find," CACM, 10/88.
Also, most simulation texts discuss random number generation in one
fashion or another, but a lot of them settle on truly horrible
generators.
-=-
-- Jeff (martens@cis.ohio-state.edu)
Ever seen a sparrow stall?andrew@teslab.lab.OZ (Andrew Phillips 289 8712) (09/27/89)
There was an very well written article by David Wood on pseudo random number
generators and the sorts of statistical tests that can be applied to test
them in the June 1988 Amiga Transactor magazine (Vol. 1, Number 2, page 38).
The disk for that issue also contained C code that implemented the tests
mentioned - written for Lattice C but I have used it under Xenix with
only very minor changes. The author emphasized that the more tests you can
perform on the PRNG the more confident you can be that it is "good". FYI
the tests were:
- Frequency test / Equi-distribution test
- Serial correlation - between digits
- Serial correlation - between every Nth digit
- Poker test
- Gap test
- Runs up/down test
- Runs above/below mean test
- Kolmogorov-Smirnov test
If anyone is interested Mr Wood also gave a network address through which
he might possibly be contacted:
!ihnp4!killer!pollux!wood
Another interesting idea that I saw in sci.crypt recently is to test a PRNG
by drawing pixels on a screen. A good one will make something that looks
like snow on a TV. The eye can very easily detect some patterns which are
caused by a poor PRNG. BTW there was also some C source code for a "good"
PRNG posted recently to sci.crypt.
--
Andrew Phillips (andrew@teslab.lab.oz{.au}) Ph. +61 (Aust) 2 (Sydney) 289 8712tomb@hplsla.HP.COM (Tom Bruhns) (09/30/89)
andrew@teslab.lab.OZ (Andrew Phillips 289 8712) writes: >. >. >. >Another interesting idea that I saw in sci.crypt recently is to test a PRNG >by drawing pixels on a screen. A good one will make something that looks >like snow on a TV. The eye can very easily detect some patterns which are >caused by a poor PRNG. ... A way to make this extremely sensitive for at least some schemes: Method A: Plot two sequential points as x and y on the screen. But only plot them if the first of the two is within a range which is very narrow compared with the range of the generated numbers. Obviously, spread its axis so that narrow range fills the screen. Method B: Draw numbers till one falls in a narrow range, as in method A. Draw two more, and plot them as X-Y. Method A will display problems in congruential generators; method B is nice to see how you have done on a binary shift register. Expect to see a pattern like a sawtooth wave for A and a pair of interleaved triangle waves for B, on the suggested generator types... >-- >Andrew Phillips (andrew@teslab.lab.oz{.au}) Ph. +61 (Aust) 2 (Sydney) 289 8712 >----------
dennis@blender.UUCP (Dennis (Grinch) Kapitan) (10/01/89)
In article <194@teslab.lab.OZ>, andrew@teslab.lab.OZ (Andrew Phillips 289 8712) writes: > There was an very well written article by David Wood on pseudo random number > generators and the sorts of statistical tests that can be applied to test > them in the June 1988 Amiga Transactor magazine (Vol. 1, Number 2, page 38). There was another article in September 1989 Amiga Transactor magazine (Vol. 2, Number 6, page 46) by Eric Giguere dealing with random number generators and testing them with the chi-square method. Dennis -- > Monday is a hard way | Dennis "Grinch" Kapitan | Send all FLAMES < > to spend one-seventh | dennis@blender.UUCP | and ICBMs to: < > of your life. | alberta!calgary!xenlink!blender | LONG: 75 45' < \_____________________/^\_______________________________/^\_LAT:___45_25'__/