3 ms·
The Box–Muller transform method (also mentioned int he article) is kind of fun. You generate two Gaussians at once. You rejection sample from the unit square
by jmount 11y ago
The Box–Muller transform method (also mentioned int he article) is kind of fun. You generate two Gaussians at once. You rejection sample from the unit square into the largest contained circle (generates a point about 3/4 of the time). You then roughly log-transform the distance along the radius (sending (0,0) to infinity) and the two points are now independent Gaussians.
- redcalx 11y agoHere's my source code for Box-Muller http://svn.code.sf.net/p/sharpneat/code/branches/V2/src/SharpNeatLib/Utility/BoxMullerGaussianSampler.cs 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.
- dbaupp 11y agoUnfortunately 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.
- redcalx 11y agoOne 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).
- semi-extrinsic 11y agoAlso, IIRC Box-Muller gives incorrect results if you're interested in sampling the tails of the Gaussian.
- onnoonno 11y agoIf 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 :-)