Ziggurat algorithm

Short description: Algorithm for pseudo-random number sampling

The ziggurat algorithm is an algorithm for pseudo-random number sampling. Belonging to the class of rejection sampling algorithms, it relies on an underlying source of uniformly-distributed random numbers, typically from a pseudo-random number generator, as well as precomputed tables. The algorithm is used to generate values from a monotonically decreasing probability distribution. It can also be applied to symmetric unimodal distributions, such as the normal distribution, by choosing a value from one half of the distribution and then randomly choosing which half the value is considered to have been drawn from. It was developed by George Marsaglia and others in the 1960s.

A typical value produced by the algorithm only requires the generation of one random floating-point value and one random table index, followed by one table lookup, one multiply operation and one comparison. Sometimes (2.5% of the time, in the case of a normal or exponential distribution when using typical table sizes) more computations are required. Nevertheless, the algorithm is computationally much faster than the two most commonly used methods of generating normally distributed random numbers, the Marsaglia polar method and the Box–Muller transform, which require at least one logarithm and one square root calculation for each pair of generated values. However, since the ziggurat algorithm is more complex to implement it is best used when large quantities of random numbers are required.

The term ziggurat algorithm dates from Marsaglia's paper with Wai Wan Tsang in 2000; it is so named because it is conceptually based on covering the probability distribution with rectangular segments stacked in decreasing order of size, resulting in a figure that resembles a ziggurat.

The Ziggurat algorithm used to generate sample values with a normal distribution. (Only positive values are shown for simplicity.) The pink dots are initially uniform-distributed random numbers. The desired distribution function is first segmented into equal areas "A". One layer i is selected at random by the uniform source at the left. Then a random value from the top source is multiplied by the width of the chosen layer, and the result is x tested to see which region of the slice it falls into with 3 possible outcomes: 1) (left, solid black region) the sample clearly under the curve and is passed directly to output, 2) (right, vertically striped region) the sample value may lie under the curve, and must be tested further. In that case, a random y value within the chosen layer is generated and compared to f(x). If less, the point is under the curve and the value x is output. If not, (the third case), the chosen point x is rejected and the algorithm is restarted from the beginning.

Theory of operation

The ziggurat algorithm is a rejection sampling algorithm; it randomly generates a point in a distribution slightly larger than the desired distribution, then tests whether the generated point is inside the desired distribution. If not, it tries again. Given a random point underneath a probability density curve, its x coordinate is a random number with the desired distribution.

The distribution the ziggurat algorithm chooses from is made up of n equal-area regions; n − 1 rectangles that cover the bulk of the desired distribution, on top of a non-rectangular base that includes the tail of the distribution.

Given a monotone decreasing probability density function f(x), defined for all x ≥ 0, the base of the ziggurat is defined as all points inside the distribution and below y₁ = f(x₁). This consists of a rectangular region from (0, 0) to (x₁, y₁), and the (typically infinite) tail of the distribution, where x > x₁ (and y < y₁).

This layer (call it layer 0) has area A. On top of this, add a rectangular layer of width x₁ and height A/x₁, so it also has area A. The top of this layer is at height y₂ = y₁ + A/x₁, and intersects the density function at a point (x₂, y₂), where y₂ = f(x₂). This layer includes every point in the density function between y₁ and y₂, but (unlike the base layer) also includes points such as (x₁, y₂) which are not in the desired distribution.

Further layers are then stacked on top. To use a precomputed table of size n (n = 256 is typical), one chooses x₁ such that x_n = 0, meaning that the top box, layer n − 1, reaches the distribution's peak at (0, f(0)) exactly.

Layer i extends vertically from y_i to y_i+1, and can be divided into two regions horizontally: the (generally larger) portion from 0 to x_i+1 which is entirely contained within the desired distribution, and the (small) portion from x_i+1 to x_i, which is only partially contained.

Ignoring for a moment the problem of layer 0, and given uniform random variables U₀ and U₁ ∈ [0,1), the ziggurat algorithm can be described as:

1. Choose a random layer 0 ≤ i < n.
2. Let x = U₀x_i.
3. If x < x_i+1, return x.
4. Let y = y_i + U₁(y_i+1 − y_i).
5. Compute f(x). If y < f(x), return x.
6. Otherwise, choose new random numbers and go back to step 1.

Step 1 amounts to choosing a low-resolution y coordinate. Step 3 tests if the x coordinate is clearly within the desired density function without knowing more about the y coordinate. If it is not, step 4 chooses a high-resolution y coordinate, and step 5 does the rejection test.

With closely spaced layers, the algorithm terminates at step 3 a very large fraction of the time. For the top layer n − 1, however, this test always fails, because x_n = 0.

Layer 0 can also be divided into a central region and an edge, but the edge is an infinite tail. To use the same algorithm to check if the point is in the central region, generate a fictitious x₀ = A/y₁. This will generate points with x < x₁ with the correct frequency, and in the rare case that layer 0 is selected and x ≥ x₁, use a special fallback algorithm to select a point at random from the tail. Because the fallback algorithm is used less than one time in a thousand, speed is not essential.

Thus, the full ziggurat algorithm for one-sided distributions is:

1. Choose a random layer 0 ≤ i < n.
2. Let x = U₀x_i
3. If x < x_i+1, return x.
4. If i = 0, generate a point from the tail using the fallback algorithm.
5. Let y = y_i + U₁(y_i+1 − y_i).
6. Compute f(x). If y < f(x), return x.
7. Otherwise, choose new random numbers and go back to step 1.

For a two-sided distribution, the result must be negated 50% of the time. This can often be done conveniently by choosing U₀ ∈ (−1,1) and, in step 3, testing if |x| < x_i+1.

Fallback algorithms for the tail

Because the ziggurat algorithm only generates most outputs very rapidly, and requires a fallback algorithm whenever x > x₁, it is always more complex than a more direct implementation. The specific fallback algorithm depends on the distribution.

For an exponential distribution, the tail looks just like the body of the distribution. One way is to fall back to the most elementary algorithm E = −ln(U₁) and let x = x₁ − ln(U₁). Another is to call the ziggurat algorithm recursively and add x₁ to the result.

For a normal distribution, Marsaglia suggests a compact algorithm:

1. Let x = −ln(U₁)/x₁.
2. Let y = −ln(U₂).
3. If 2y > x², return x + x₁.
4. Otherwise, go back to step 1.

Since x₁ ≈ 3.5 for typical table sizes, the test in step 3 is almost always successful.

Optimizations

The algorithm can be performed efficiently with precomputed tables of x_i and y_i = f(x_i), but there are some modifications to make it even faster:

• Nothing in the ziggurat algorithm depends on the probability distribution function being normalized (integral under the curve equal to 1), removing normalizing constants can speed up the computation of f(x).
• Most uniform random number generators are based on integer random number generators which return an integer in the range [0,  2³² − 1]. A table of 2⁻³²x_i lets you use such numbers directly for U₀.
• When computing two-sided distributions using a two-sided U₀ as described earlier, the random integer can be interpreted as a signed number in the range [−2³¹, 2³¹ − 1], and a scale factor of 2⁻³¹ can be used.
• Rather than comparing U₀x_i to x_i+1 in step 3, it is possible to precompute x_i+1/x_i and compare U₀ with that directly. If U₀ is an integer random number generator, these limits may be premultiplied by 2³² (or 2³¹, as appropriate) so an integer comparison can be used.
• With the above two changes, the table of unmodified x_i values is no longer needed and may be deleted.
• When generating IEEE 754 single-precision floating point values, which only have a 24-bit mantissa (including the implicit leading 1), the least-significant bits of a 32-bit integer random number are not used. These bits may be used to select the layer number. (See the references below for a detailed discussion of this.)
• The first three steps may be put into an inline function, which can call an out-of-line implementation of the less frequently needed steps.

Generating the tables

It is possible to store the entire table precomputed, or just include the values n, y₁, A, and an implementation of f⁻¹(y) in the source code, and compute the remaining values when initializing the random number generator.

As previously described, you can find x_i = f⁻¹(y_i) and y_i+1 = y_i + A/x_i. Repeat n − 1 times for the layers of the ziggurat. At the end, you should have y_n = f(0). There will be some round-off error, but it is a useful sanity test to see that it is acceptably small.

When actually filling in the table values, just assume that x_n = 0 and y_n = f(0), and accept the slight difference in layer n − 1's area as rounding error.

Finding x₁ and A

Given an initial (guess at) x₁, you need a way to compute the area t of the tail for which x > x₁. For the exponential distribution, this is just e^−x₁, while for the normal distribution, assuming you are using the unnormalized f(x) = e^−x2/2, this is √π/2 erfc(x/√2). For more awkward distributions, numerical integration may be required.

With this in hand, from x₁, you can find y₁ = f(x₁), the area t in the tail, and the area of the base layer A = x₁y₁ + t.

Then compute the series y_i and x_i as above. If y_i > f(0) for any i < n, then the initial estimate x₁ was too low, leading to too large an area A. If y_n < f(0), then the initial estimate x₁ was too high.

Given this, use a root-finding algorithm (such as the bisection method) to find the value x₁ which produces y_n−1 as close to f(0) as possible. Alternatively, look for the value which makes the area of the topmost layer, x_n−1(f(0) − y_n−1), as close to the desired value A as possible. This saves one evaluation of f⁻¹(x) and is actually the condition of greatest interest.

References

• George Marsaglia; Wai Wan Tsang (2000). "The Ziggurat Method for Generating Random Variables". Journal of Statistical Software 5 (8). http://www.jstatsoft.org/v05/i08/paper. Retrieved 2007-06-20.  This paper numbers the layers from 1 starting at the top, and makes layer 0 at the bottom a special case, while the explanation above numbers layers from 0 at the bottom.
• C implementation of the ziggurat method for the normal density function and the exponential density function, that is essentially a copy of the code in the paper. (Potential users should be aware that this C code assumes 32-bit integers.)
• A C# implementation of the ziggurat algorithm and overview of the method.
• Jurgen A. Doornik (2005). "An Improved Ziggurat Method to Generate Normal Random Samples". Nuffield College, Oxford. http://www.doornik.com/research/ziggurat.pdf.  Describes the hazards of using the least-significant bits of the integer random number generator to choose the layer number.
• Normal Behavior By Cleve Moler, MathWorks, describing the ziggurat algorithm introduced in MATLAB version 5, 2001.
• The Ziggurat Random Normal Generator Blogs of MathWorks, posted by Cleve Moler, May 18, 2015.
• David B. Thomas; Philip H.W. Leong; Wayne Luk; John D. Villasenor (October 2007). "Gaussian Random Number Generators". ACM Computing Surveys 39 (4): 11:1–38. doi:10.1145/1287620.1287622. ISSN 0360-0300. http://www.doc.ic.ac.uk/~wl/papers/07/csur07dt.pdf. Retrieved 2009-07-27. "[W]hen maintaining extremely high statistical quality is the first priority, and subject to that constraint, speed is also desired, the Ziggurat method will often be the most appropriate choice.".  Comparison of several algorithms for generating Gaussian random numbers.
• Nadler, Boaz (2006). "Design Flaws in the Implementation of the Ziggurat and Monty Python methods (And some remarks on Matlab randn)". arXiv:math/0603058.. Illustrates problems with underlying uniform pseudo-random number generators and how those problems affect the ziggurat algorithm's output.
• Edrees, Hassan M.; Cheung, Brian; Sandora, McCullen; Nummey, David; Stefan, Deian (13–16 July 2009). "Hardware-Optimized Ziggurat Algorithm for High-Speed Gaussian Random Number Generators". 2009 International Conference on Engineering of Reconfigurable Systems & Algorithms. Las Vegas. http://www.ee.cooper.edu/~nummey/ersa2009.pdf.