Ziggurat algorithm
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.
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Amount105107765
- Attribute100024264
- Event100029378
- Magnitude105090441
- Number105121418
- Procedure101023820
- Property104916342
- PsychologicalFeature100023100
- Rule105846932
- software
- WikicatNon-uniformRandomNumbers
- WikicatStatisticalAlgorithms
- YagoPermanentlyLocatedEntity
- Comment
- enThe 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.
- Depiction
- Has abstract
- enThe 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.
- Hypernym
- Algorithm
- Is primary topic of
- Ziggurat algorithm
- Label
- enZiggurat algorithm
- Link from a Wikipage to an external page
- apps.dtic.mil/sti/citations/AD0423993
- web.archive.org/web/20140910003249/http:/www.dtic.mil/docs/citations/AD0423993
- www.doc.ic.ac.uk/~wl/papers/07/csur07dt.pdf
- www.ee.cooper.edu/~nummey/ersa2009.pdf
- blogs.mathworks.com/cleve/2015/05/18/the-ziggurat-random-normal-generator/
- au.mathworks.com/company/newsletters/articles/normal-behavior.html
- www.jstatsoft.org/v05/i08/paper
- www.jstatsoft.org/article/downloadSuppFile/v005i08/rnorrexp.c
- www.doornik.com/research/ziggurat.pdf
- heliosphan.org/zigguratalgorithm/zigguratalgorithm.html
- Link from a Wikipage to another Wikipage
- Algorithm
- Bisection method
- Box–Muller transform
- Category:Non-uniform random numbers
- Category:Pseudorandom number generators
- Category:Statistical algorithms
- Defense Technical Information Center
- Error function
- Exponential distribution
- File:Ziggurat method.gif
- Gaussian distribution
- George Marsaglia
- IEEE 754
- Inline function
- Marsaglia polar method
- MATLAB
- Monotonic function
- Normal distribution
- Normalizing constant
- Numerical integration
- Probability distribution
- Pseudo-random number generator
- Pseudo-random number sampling
- Recursion
- Rejection sampling
- Root-finding algorithm
- Round-off error
- Sanity test
- Symmetric function
- Unimodal distribution
- Ziggurat
- SameAs
- 2gi1F
- Algoritmo ziggurat
- m.0h3sx1
- Méthode ziggourat
- Q2894386
- Ziggurat algorithm
- Алгоритм Зиккурат
- שיטת זיגורט
- الگوریتم زیگورات
- Subject
- Category:Non-uniform random numbers
- Category:Pseudorandom number generators
- Category:Statistical algorithms
- Thumbnail
- WasDerivedFrom
- Ziggurat algorithm?oldid=1102322020&ns=0
- WikiPageLength
- 17519
- Wikipage page ID
- 7093060
- Wikipage revision ID
- 1102322020
- WikiPageUsesTemplate
- Template:Citation needed
- Template:Cite arXiv
- Template:Cite conference
- Template:Cite document
- Template:Cite journal
- Template:Cite techreport
- Template:Short description
- Template:Sqrt
