Normal/Gaussian random number generation for D

jerro a at a.com
Wed Oct 24 12:41:26 PDT 2012


> Can you expand on this, and maybe provide a reference?  I don't 
> doubt your code's effectiveness but I think where RNGs are 
> concerned we really need to be able to justify our algorithmic 
> choices.  There's too much literature out there showing how 
> commonly-used algorithms actually carry statistical flaws.

The first change I made to the algorithm is shifting layer 
boundaries. Basic Ziggurat algorithm uses n layers with area A. 
Because computing samples from the bottom layer and the top layer 
is typically more expensive than computing samples from other 
layers, I shifted the layer boundaries so that the top and the 
bottom layers have areas A / 2 and other n - 1 layers have area 
A. That way we only need to draw half as many samples from the 
top and the bottom layer.

To better describe the second change, I drew a picture and 
uploaded it to http://i.imgur.com/bDRpP.png . The basic Ziggurat 
algorithm first chooses the layer randomly and then chooses a 
random number x between 0 and xavg. If x is below xmin, it 
returns it. The algorithm I use does this too. When x is above 
xmin, the basic Ziggurat algorithm chooses a random point in the 
outer layer area (see the picture), checks if y < f(y), returns 
its x coordinate if it is, and chooses a new point otherwise. My 
algorithm uses precomputed low and high x offsets for each layer. 
It chooses a point below the high diagonal, and checks if it is 
below the low diagonal. If it is (and it is in most cases), it 
returns its x coordinate without computing f(x). If only checks 
if y < f(x) when y is above the low diagonal. That way it doesn't 
need to make as many calls to f(x).


More information about the Digitalmars-d mailing list