Hacker News Reader

Here's my source code for Box-Muller

http://svn.code.sf.net/p/sharpneat/code/branches/V2/src/Shar...

Note it's a lot simpler (more elegant) than the Ziggurat method!

Also note the while loop rejects sqr==0 because that would cause Log(0) to throw an exception. I convinced myself that was correct when I wrote it in 2011, but I'm struggling to remember how I came to that conclusion.

View on HN

Unfortunately the elegance comes at a cost: Box-Muller is a lot slower due to the sqrt and log. Ziggurat's fast path (which can be hit arbitrarily rarely, by controlling the table size) is just some indexing and comparisons, making it amazingly fast.

Also, Ziggurat can be applied to any distribution with a decreasing PMF (e.g. it's also amazingly fast for the Exponential distribution), whereas Box-Muller relies on special properties of the Normal.

One could say that the high level source code is elegant, but overall its use of log and sqrt invoke a lot of complex machinations (inside the CPU).

Also, IIRC Box-Muller gives incorrect results if you're interested in sampling the tails of the Gaussian.

If you're not interested in the tails, there's also always

(random()+random()+random()+random()-2.0)*sqrt(3.)

as a cheap (in terms of brain power) Gaussian (sigma=1, mean=0) rough approximation :-)

Reply on news.ycombinator.com