Reference implementations of random number generators
Brad Lucier 14 Feb 2002 08:26 UTC
I'm impressed with your SRFI. In the past, there have been some truly
awful RNG algorithms published in well-known places, and then used by
many people. This is not the case here---the COMBO RNG is quite good.
I am bothered, though, by the relative lack of theoretical justification
for combination RNGs. As Marsaglia says at the end of his keynote.ps file,
"if the numbers are not random, they are at least higgledy piggledy".
Basically, I guess I'm too much a mathematician to bring myself to trust
"higgledy piggledy" generators that do not have strong theoretical
justifications.
I've been impressed with what Pierre L'Ecuyer calls "combined multiple
recursive random number generators", see his web site at
http://www.iro.umontreal.ca/~lecuyer
See specifically his paper "Good parameters and implementations for
combined multiple recursive random number generators". These generators
pass the spectral tests of Knuth, volume 2, for large dimensions.
They also pass Marsaglia's tests in Diehard (at least, as much as I
can interpret them---Marsaglia does not give a whole lot of advice on
how he judged whether one should put "Pass" or "Fail" in the boxes of
his summary table in keynote.ps).
I've posted the paper cited above, together with the results of all
diehard tests on combo and a scheme implementation of L'Ecuyer's
method at my web site
http://www.math.purdue.edu/~lucier/random
I believe that L'Ecuyer's generator would make a better choice for
a reference implementation. Perhaps I'd just like to see a discussion
of the pros and cons of various possible implementations.
Brad Lucier