The Ziggurat Algorithm — or — Generating Normally-Distributed Random Numbers

The Ziggurat Algorith

(originally titled The Ziggurat Algorithm — Generating Normally-Distributed Random Numbers)

Random number generators, or RNGs, are fascinating bits of abstract mathematics, wrapped up in real-world engineering to deliver a practical solution for an everyday problem: give me an arbitrary number.

RNG designers try very hard to ensure that the distribution of randomness is uniform. Sometimes, you need a normal distribution of random numbers.

Let me introduce you to my old friend, the Gaussian Distribution:

$$f(x) = e^{-x^2/2}$$

Finding normally-distributed random numbers is devilishly simple: generate uniform random numbers, projected onto the 2-dimensional Cartesian plane, and then run the Gaussian pdf (probability density function):

If the y-component of the projection lies above \(f(x)\), we reject that random number and try again. This is called a rejection method.

Here are some pretty rectangles:

James works on the Internet, spends his weekends developing new and interesting bits of software and his nights trying to make sense of research papers.

Currently exploring just how much data you can shove though DuckDB before it explodes.