I did not receive this message until the Big Crush test was well
advanced, so I let it finish.
It took almost 30 hours to run on the system that I described and
reported that all of the tests were passed. I will rerun the test on
the new CVS version when you are satisfied with it.
However, people might hold off for a bit with the crush tests. I
think I now see what's going on. I'm no expert on RNGs, but here
1) The main speed advantage from ziggurat is that (in the original
Marsaglia/Tsang version) it requires the generation of only one
random 32-bit integer per normal sample, where Box-Muller requires
2) However, Doornik points out that there's a problem with this,
which emerges if you want to generate normally distributed
"doubles" (64-bit floating point values -- the original ziggurat
generated 32-bit "floats"). The trouble is that if you use just
one set of 32 bits to select the ziggurat box or level and for the
uniform value to be tested for acceptance at that level, you get a
certain sort of subtle dependence, and the symptom is that the
normal RNG fails Knuth's collisions test (on the regular crush
suite as well as big crush).
3) I took Jochen Voss's ziggurat code and adapted it for gretl,
and it passed all the tests. So at first I thought we'd somehow
got around Doornik's problem (maybe by using a better RNG for the
initial uniform input).
4) But then I took a closer look at the Voss code, and I see that
it dodges the dependence problem by a means that Doornik mentions
but does not recommend. Namely, from the initial 32-bit input it
7 bits for the ziggurat level
1 bit for the sign
24 bits for the value to be tested
There's no dependence problem because Voss uses non-overlapping
bits for the box selector and the test value (and so one can quite
confidently predict that this generator will pass the collisions
test), but the drawback is that one can then generate "only" about
30 million distinct normal values.
5) To get better coverage of the real line one can use one and a
quarter random ints per normal draw. For example, one can use 7
bits for selecting a box, one for the sign, and 30 for the test
value, to get about 10^9 distinct normal values (with 2 bits of
I've now implemented this in gretl and I'm running the crush suite
right now. If it passes (in principle it should, but I might have
screwed something up in regard to the quarter-ints), I'll commit
it to CVS and then people can try attacking it with big crush.
Gretl-devel mailing list
End of Gretl-devel Digest, Vol 35, Issue 23