The Ziggurat Method for Generating Random Variables

By George Marsaglia, Wai Wan Tsang. 2000

703 citations recorded by the source corpus.

We provide a new version of our ziggurat method for generating a random variable from a given decreasing density. It is faster and simpler than the original, and will produce, for example, normal or exponential variates at the rate of 15 million per second with a C version on a 400MHz PC. It uses two tables, integers ki, and reals wi. Some 99% of the time, the required x is produced by: Generate a random 32-bit integer j and let i be the index formed from the rightmost 8 bits of j. If j

Subfields: Artificial Intelligence, Statistics and Probability, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Algorithms & Complexity

Citations in the corpus

Array programming with NumPy (2020, methodology): “[67] G.”
A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, background): “Additional approaches that are more efficient on average but slow in the worst-case scenario have been described in [40].”
MatConvNet: Convolutional Neural Networks for MATLAB (2014, methodology): “1 Normal sampler The function vl::randn() uses the Ziggurah method [10] to sample from a Normallydistributed random variable.”
Cambricon: An Instruction Set Architecture for Neural Networks (2016, methodology): “, Gaussian distribution) using the Ziggurat algorithm [31], with the help of vector arithmetic instructions and vector compare instructions in Cambricon.”
FAST MONTE CARLO SIMULATION METHODS FOR BIOLOGICAL REACTION-DIFFUSION SYSTEMS IN SOLUTION AND ON SURFACES (2008, methodology): “Depending on the approach, speeds can be substantially slower (polar form of the Marsaglia Gaussian method [9]) and at best may improve by less than 2% (ziggurat Gaussian method [10]).”
Improved Consistent Sampling, Weighted Minhash and L1 Sketching (2010, methodology): “Alternatively, we can use the efficient Ziggurat method [12].”
A simple method for generating gamma variables (2000, methodology): “In terms of both speed and size, we have chosen to use a new implementation of our ziggurat method [Marsaglia and Tsang 2000], providing the required RNOR most of the time in-line, in C.”
Evaluating the Anderson-Darling Distribution (2004, methodology): “This can be done using the ziggurat method of Marsaglia and Tsang [5], with the #define feature of C that permits the fast part of the generating procedure to be done in-line.”
Secure multiparty aggregation with differential privacy: a comparative study (2013, methodology): “Additional approaches, which are more efficient on average but slow in the worst-case scenario, have been introduced in [31,32].”