This repo. contains the results from my 3 month summer internship at the University of Toronto under the supervision of Prof. Frank Kschischang in 2014.

• A Report on the Ziggurat Method
• How to reference this repo.
• Files
• Compile LaTeX
• Abstract
• Related Work
• References

@article{daniel severo_2019, 
  title={A Report on the Ziggurat Method},
  DOI={10.5281/zenodo.3546269},
  abstractNote={Mathematical proof of functionality, of a highly efficient pseudo-random number generator: The Ziggurat Method}, 
  publisher={Zenodo},
  author={Daniel Severo},
  year={2019},
  month={Nov}}

• Full report
• Slides

Run make report or make slides to compile the respective files from tex/ to build/. You will need the following:

apt install texlive latexmk texlive-fonts-extra texlive-pictures

Pseudo-random number generators (PRNG's) are crucial in the context of simulating noise in communication channels. We present a report on an efficient method for generating pseudo-random samples from any decreasing probability distribution called the Ziggurat Method. The initial idea was developed by [1], but has been enhanced by Marsaglia, Tsang [3] and others. Specifically, we will show the latest and most efficient version presented by McFarland [4]. In the latter paper, the method shows a speedup of over 3 times compared to traditional algorithms such as Marsaglia's Polar Method [2]. We present a speed comparison in C implemented on an Intel i7-4790 clocked at 3.60 GHz. McFarland [4] provides all the necessary code to implement an ad hoc version of the algorithm, as well as a ready-to-use C code for a univariate Gaussian. A proof that the samples from this method are truly Gaussian is also provided.

• ZMG: Ziggurat Method Generator of Zero-Mean Gaussians.

[1] George Marsaglia, ”A convenient method for generating normal variables.”, SIAM Rev. 6, 260-264,1964.

[2] George Marsaglia, Wai Wan Tsang, ”A fast, easily implemented method for sampling from de-creasing or symmetric unimodal density functions”, SIAM Journ. Scient. and Statis. Computing,5, 349-359, 1984.

[3] George Marsaglia, Wai Wan Tsang, ”The Ziggurat Method for Generating Random Variables”,Journal of Statistical Software, 2000.

[4] Christopher D. McFarland, ”A modified ziggurat algorithm for generating exponentially- andnormally-distributed pseudorandom numbers.”, Apr. 2014.