A modified ziggurat algorithm for generating exponentially and normally distributed pseudorandom numbers. Issue 7 (2nd May 2016)

• Record Type: Journal Article
• Authors: McFarland, Christopher D.
• Is Part Of: Journal of statistical computation and simulation. Volume 86:Issue 7(2016)
• Page Start: 1281
• Page End: 1294
• Publication Date: 2016-05-02
• Subjects: Mathematical statistics -- Data processing -- Periodicals; Digital computer simulation -- Periodicals; 519.5028505
• DOI: 10.1080/00949655.2015.1060234
• Languages: English
• ISSNs: 0094-9655

Abstract

Abstract : The ziggurat algorithm is a very fast rejection sampling method for generating pseudorandom numbers (PRNs) from statistical distributions. In the algorithm, rectangular sampling domains are layered on top of each other (resembling a ziggurat) to encapsulate the desired probability density function. Random values within these layers are sampled and then returned if they lie beneath the graph of the probability density function. Here, we present an implementation where ziggurat layers reside completely beneath the probability density function, thereby eliminating the need for any rejection test within the ziggurat layers. In the new algorithm, small overhanging segments of probability density remain to the right of each ziggurat layer, which can be efficiently sampled with triangularly shaped sampling domains. Median runtimes of the new algorithm for exponential and normal variates is reduced to 58% and 53%, respectively (collective range: 41–93%). An accessible C library, along with extensions into Python and MATLAB/Octave are provided.