[Gretl-devel] Subject: Re: simulation speed

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 goes... 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 two. 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 uses: 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 "wastage"). 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. Allin. ------------------------------ _______________________________________________ Gretl-devel mailing list Gretl-devel(a)lists.wfu.edu http://lists.wfu.edu/mailman/listinfo/gretl-devel End of Gretl-devel Digest, Vol 35, Issue 23 *******************************************