Random number generators: thanks and brief summary
Oleg Goldshmidt
Some weeks ago I posted a query in this newsgroup asking for
suggestions and pointers to good random number generators (RNG).
I got quite a few very helpful and informative responses, both as
newsgroup postings and as personal email. There were lots of useful
pointers to web sites and papers, interesting tips, even lists of
references. I would like to thank everybody who replied - you guys
have saved me a lot of time and effort.
For those who are interested in a summary (the rest should read
further only in search for good reasons to flame), here is a brief
one. Disclaimer up front: this has no more value than any newsgroup
posting. I am sharing the generalities of my homework, you should do
yours and verify that it works for you as well as it worked for me. I
have no incentive, material or otherwise, to promote, or sling mud on
any particular RNG. I also emphasize that this is only a brief and
generic summary, not a comprehensive report.
It is rather amazing how many different roads eventually lead to
one place. Searching for _good_ RNGs almost invariably brings you
to the work of George Marsaglia. You can find some pretty good and
efficient RNGs in his papers, and the clinch is the DIEHARD battery
of tests that he developed for determining how random the generated
numbers are. If you are interested, try
http://stat.fsu.edu/~geo/diehard.html.
Look into Knuth's "The Art of Computer Programming" for the underlying
theory. Using DIEHARD is not difficult, though it is not the most
intuitive tool.
Well, take your favourite RNG and check how lousy it is. I suggest you
do it yourself: we found that while Marsaglia says in one of his 1993
(if I am not mistaken, I don't have the paper handy at the moment)
that ran2 from "Numerical Recipes" is OK, it didn't pass DIEHARD of
1996 (according to the logs in the code) vintage. Well, it passed some
of the tests but not the others. The only explanation I have for this
discrepancy is that the tests became more stringent in the intervening
period.
I think that randlib is a rather popular library of RNGs. We found it
to be of moderate quality.
Marsaglia's papers contain whole families of RNGs. Many are very good,
both in terms of "randomness" and in terms of efficiency.
The Mersenne Twister (http://www.math.keio.ac.jp/~matumoto/emt.html)
looks very good.
For Linux users out there: did you know that you can read random bytes
from /dev/urandom? Look into /usr/src/linux/drivers/char/random.c for
documentation (very well written, and great idea, I think). It is
supposed to be cryptographically strong, and it also passes DIEHARD
with flying colors, so it could be used for simulations were it not
for one disadvantage: it is rather slow compared with good
"algorithmic" RNGs.
Finally, I often encountered variants of the following statement:
"I really don't believe that for any typical problem but the most
convoluted and artificial ones any widely used RNG would fail"
Well, we saw on the most trivial example (really!) how ran1 from
"Numerical Recipes" gave blatantly wrong results, while one of
Marsaglia's RNGs produced the right ones, being also much faster.
So do test your favourite RNG, or risk publishing a wrong result.
Many thanks again to everybody who replied to my original question.
--
Oleg Goldshmidt
gold...@netvision.net.il