Ziggurat Algorithm¶

A table-driven rejection sampler that partitions a monotone density into equal-area horizontal layers, making most draws a fast interior test while routing overhang and tail cases to exact fallback tests.

Version: v1 · 2026-08-30 · History
Domain-specific #: 3143
Origin domain: random variate generation
Subdomain: rejection sampling
Aliases: Ziggurat Method

Core Idea¶

The Ziggurat Algorithm is a table-driven rejection-sampling method for drawing pseudorandom variates from a decreasing density, or from one half of a symmetric unimodal density. Before sampling begins, it partitions the area under the density into equal-area horizontal strips and stores their boundary coordinates. The rectangles resemble a stepped ziggurat. During sampling, a uniformly selected strip and a uniformly generated horizontal coordinate usually land inside an interior region known in advance to lie below the density. That common path needs only integer selection, a table lookup, multiplication, and comparison. Only a small minority of points reach an overhang where the density must be evaluated, or the unbounded base strip where a separate tail sampler is required.

Scope of Application¶

The canonical scope is high-throughput generation from normal and exponential distributions. More generally, the method applies directly to decreasing densities and, through reflection or sign selection, to symmetric unimodal densities. Marsaglia and Tsang describe the distribution-general construction and optimized normal/exponential versions. The method is valuable in simulation, stochastic optimization, Bayesian computation, queueing models, communications, and any workload where many target-distributed variates are required after a one-time table setup.

Clarity¶

The layered picture separates distributional correctness from performance engineering. Correctness comes from equal proposal mass, complete coverage, and exact accept/reject routing. Performance comes from making the certified interior occupy most of each selected layer. Increasing the number of layers normally shrinks overhang area and makes the fast path more frequent, but enlarges tables and can alter cache behavior.

Manages Complexity¶

Direct evaluation of logarithms, exponentials, square roots, or trigonometric functions on every draw can dominate a high-volume simulation. The ziggurat shifts work from runtime to preprocessing. The stored table compresses the target density's geometry into widths, thresholds, and height differences. Most draws then require only cheap operations; exact functions are reserved for rare ambiguous regions and tails.

Abstract Reasoning¶

For a decreasing density \(f\) on \(x\ge0\), choose boundaries

\[ 0=x_n < x_{n-1}<\cdots <x_1<x_0=r \]

so that the designated strip regions have common area \(V\), with the base accounting for the tail beyond \(r\). Uniform layer selection is then valid because each layer represents equal probability mass. Inside a selected rectangle, the segment \(0\le X<x_{i+1}\) lies wholly below the next lower density boundary and is accepted without another uniform height coordinate.

Knowledge Transfer¶

Literal transfer occurs from the exponential density to the positive half of the normal density and to other decreasing or symmetric unimodal densities for which equal-area boundaries and a tail sampler can be constructed. The table layout, layer-selection logic, interior certificate, overhang test, and tail role transfer; only the density, constants, and specialized tail routine change.

Transfer to arbitrary multidimensional or multimodal targets is not automatic. One may design layered rejection proposals there, but the canonical one-dimensional ziggurat identity should not be claimed unless the equal-area indexed architecture and exact routing survive.

Relationships to Other Abstractions¶

Current abstraction Ziggurat Algorithm Domain-specific

Parents (1) — more general patterns this builds on

Ziggurat Algorithm is a kind of Algorithm Prime

Ziggurat Algorithm is a strict specialization of prime:algorithm: it is a finite executable procedure with precomputation, random inputs, branching tests, and an output contract.

Hierarchy paths (2) — routes to 2 parentless roots

Ziggurat Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Ziggurat Algorithm sits in a sparse region of the domain-specific corpus (80^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08