Everything about Ziggurat algorithm
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. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Ziggurat algorithmA 5-minute orientation
- Read the landmark paper: A modified ziggurat algorithm for generating exponentially and normally distributed pseudorandom numbersCited 7 times
- Go sideways: Random permutationA closely related topic
- Go sideways: Box–Muller transformA closely related topic
đź“– Definitions
Noun An algorithm for pseudorandom number sampling, relying on an underlying source of uniformly-distributed random numbers as well as computed tables.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
đź“š Books worth reading
Open Library didn't respond; try again in a moment.
đź”— Related topics
- Random permutation A random permutation is a sequence where any order of its items is equally likely at random, that is, it is a permutation-valued random variable of a set…
- Box–Muller transform In mathematics, the Box–Muller transform, introduced by George Edward Pelham Box and Mervin Edgar Muller, is a random number sampling method for generating…
- Non-uniform random variate generation Non-uniform random variate generation or pseudo-random number sampling is the numerical practice of generating pseudo-random numbers (PRN) that follow…
- Probability density function In probability theory, a probability density function (PDF), density function, or simply density of an absolutely continuous random variable, is a function…
- Truncated normal distribution In probability and statistics, the truncated normal distribution is the probability distribution derived from that of a normally distributed random variable…
- Inverse transform sampling Inverse transform sampling (also known as inversion sampling, the inverse probability integral transform, the inverse transformation method, or the Smirnov…
- Mersenne Twister The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士)…
- Reservoir sampling Reservoir sampling is a family of randomized online algorithms for choosing a simple random sample, without replacement, of k items from a population of…