Pipelining the Ziggurat Random Number Generator

Question

I'm currently implementing a version of George Marsaglia's Ziggurat random number generator. Although it is supposedly one of the fastest ways to generate good quality normally-distributed random number generators, it is full of loop control code (ie. return statements in the middle of a loop, if-statements, branches, etc) and it makes several calls to standard C functions like exp() and log(). Not to mention the infinite loop.

This makes for code that cannot be pipelined by the compiler. Ultimately, I feel like a basic approach, such as using the central limit theorem directly, might ultimately be faster since it can be pipelined easily. Unfortunately, it is not suitable for the tails of the Gaussian distribution and therefore it's not acceptable for my application.

Does anybody here have any ideas on how control code and function calls might be reduced. I am currently using Colin Green's implementation of the algorithm that I ported to C. My underlying uniform generator is the Tiny Mersenne Twister (so please don't tell me to use the MT as I've seen other people do, I'm already there. This discussion is for normally-distributed RNG's, not uniform RNG's).

Answer 1

You might take a look at my C implementation here. The main function is only 20-something lines of code, so should be easy to unroll the loop a bit. It also gives you the choice of using integer or float compares, whichever is faster on your machine. You can plug in any back-end RNG.