2013/03/31 by Charles F. F. Karney · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #Chaos-based Image/Signal Encryption #Complexity and Algorithms in Graphs #Cryptography and Data Security #cs.MS #math.PR #physics.comp-ph
paper · pdf · doi:10.1145/2710016
published as ACM Trans. Mathematical Software 42(1), 3:1-14 (Jan. 2016) · LaTeX, 8 pages, 1 figure. Revision includes algorithm for sampling discrete normal distribution. An implementation of the algorithms is available at http://exrandom.sf.net
arxiv created 2014/06/10 · openalex publication_date 2016/01/29 · arxiv updated 2016/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An algorithm for sampling exactly from the normal distribution is given. The algorithm reads some number of uniformly distributed random digits in a given base and generates an initial portion of the representation of a normal deviate in the same base. Thereafter, uniform random digits are copied directly into the representation of the normal deviate. Thus, in contrast to existing methods, it is possible to generate normal deviates exactly rounded to any precision with a mean cost that scales linearly in the precision. The method performs no extended precision arithmetic, calls no transcendental functions, and uses no floating point arithmetic whatsoever; it uses only simple integer operations. It can easily be adapted to sample exactly from the discrete normal distribution whose parameters are rational numbers.