Lib rand

Generating random numbers, and sampling from random distributions.

1. Announcement to mailing list

• Proposed editor: Huon Wilson (@huonw)
• Date proposed: date of proposal
• Link: link to email

Notes from discussion on mailing list

• first discussion

2. Research of standards and techniques

1. Standard: standard - link to docs - ...

2. Standard: standard - link to docs - ...

3. Technique: Generating random bits/numbers (i.e u32 or u64) - http://en.wikipedia.org/wiki/List_of_random_number_generators - http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator - ISAAC/ISAAC-64 RNG

   • cryptographically secure
   • http://burtleburtle.net/bob/rand/isaacafa.html
   • ISAAC is the main RNG used in rust at the moment
   • I've found little/no information about ISAAC-64
   • "On the pseudo-random generator ISAAC" Aumasson 2006 (details some problems in ISAAC and proposes a slight improvement ISAAC+) - Mersenne Twister
   • "The Mersenne twister is the default random number generator for Python,[7][8] Ruby,[9] R,[10] PHP,[11] MATLAB and also available in C++[12] since C++11."
   • "The algorithm in its native form is not suitable for cryptography"
   • SIMD-oriented Fast Mersenne Twister (SFMT)
     • dSFMT is used by Julia, and possibly Erlang
   • A fairly straight translation of the C of the 32 and 64 bit variants of MT19937 appears to be ~10% slower than ISAAC and ISAAC-64 respectively (benchmarks here) - Xorshift
   • Not crypto quality, but simple, small and fast
   • Currently the only other RNG in Rust
   • "On the Xorshift Random Number Generators" Panneton & L'Ecuyer 2005(?) (analysis of and improvements to the xorshift generators) - LFSR, aka Tausworthe generators
   • Not crypto quality, fast
   • "Tables of maximally equidistributed combined LSFR generators" L'Ecuyer 1999 (includes a 64 bit variant)
   • "Maximally Equidistributed Combined Tausworthe Generators" L'Ecuyer 1996
   • "Random Numbers Generated by Linear Recurrence Modulo Two" Tausworthe 1965 - WELL
   • Better randomness properties than Mersenne twister
   • Fairly fast public domain implementation on p8 of http://www.lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf (this is an overview of multiple RNG algorithms) - MWC/CMWC
   • Not crypto quality, fast
   • "Random Number Generators" Marsaglia 2003 (pages 6-17, also relevant to xorshift) - Wichmann Hill
   • "Generating good pseudo-random numbers" Wichmann-Hill 2005 - Hardware
   • RDRAND on Ivy Bridge x64 CPUs (example of use in a Haskell package) - Assorted names: YARN5, Lagged Fibonacci, Multiple recurrence

4. Technique: Testing quality of random numbers - Very important! Extremely hard to tell if random numbers are "random enough" (a bug in an implementation, or a bad algorithm, can produce numbers that look random but aren't random enough for many purposes). - Overview wikipedia article - Diehard tests (e.g. dieharder) - TestU01 including "Small crush", "Crush" and "Big crush" - tests written by the creator of ISAAC - ENT - NIST - Add a new make target "check-rngs" with a testsuite?

5. Technique: sampling from distributions - Converting ints to floats:

   • Most languages/implementations just multiply the random int by 2**-num_bits to get a float in [0,1).
   • "Conversion of High-Period Random Numbers to Floating Point" Doornik 2006 - General:
   • Inverse transform sampling
   • Ziggurat algorithm (any distribution with decreasing density functions)
   • "The Monty Python method for generating random variables" Marsaglia & Tsang 1998 (similar to Ziggurat, except slightly slower and doesn't require tables.) - Normal
   • Box-Muller transform and Marsaglia polar method (normal distribution, both are almost certainly inferior to the ziggurat algorithm)
   • "Gaussian Random Number Generators" Thomas, Luk, Leong, Villasenor 2007 (extremely comprehensive overview of many algorithms for normal RVs, including performance and statistical comparisons. Their conclusion is Ziggurat is fast and statistically good.)
   • "Efficient generation of exponential and normal deviates" Rubin, Johnson 2006 (also describes/addresses deficiencies of the plain Marsaglia Ziggurat implementation) - Gamma
   • "A simple method for generating gamma variables" Marsaglia & Tsang 2000
   • "A Simple Gamma Random Number Generator for Arbitrary Shape Parameters" Tanizaki 2008
   • https://hips.seas.harvard.edu/blog/2013/02/21/a-parallel-gamma-sampling-implementation/

Summary of research on standards and leading techniques

Relevant standards and techniques exist?

Those intended to follow (and why)

Those intended to ignore (and why)

3. Research of libraries from other languages

1. Language: C++11 - http://www.cplusplus.com/reference/random/
2. Language: Python - http://docs.python.org/3.3/library/random.html
3. Language: R (statistical language, so much broader random number support than necessary) - http://stat.ethz.ch/R-manual/R-patched/library/base/html/Random.html - http://stat.ethz.ch/R-manual/R-patched/library/stats/html/Distributions.html - Parallel random numbers (section 6): http://stat.ethz.ch/R-manual/R-devel/library/parallel/doc/parallel.pdf
4. Language: Julia (also a statistical language) - https://github.com/JuliaStats/Distributions.jl
5. Language: D - http://dlang.org/phobos/std_random.html (no support for sampling from distributions other than uniform, but many RNGs)
6. Language: Go - http://golang.org/pkg/math/rand/
7. Language: Erlang - https://mail.mozilla.org/pipermail/rust-dev/2013-April/003881.html
8. Library: GSL - https://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generation.html - https://www.gnu.org/software/gsl/manual/html_node/Random-Number-Distributions.html
9. Library: Numpy/Scipy - http://docs.scipy.org/doc/numpy/reference/routines.random.html - http://docs.scipy.org/doc/scipy/reference/stats.html
10. Library: Boost - http://www.boost.org/doc/libs/1_53_0/doc/html/boost_random/reference.html
11. Library: RandomKit
12. Library: Tina's Random Number Generator Library - Includes many distributions, also support for/discussion about parallel RNGs.
13. Misc: - http://tommd.github.io/posts/RNG-Bench.html - http://hackage.haskell.org/package/crypto-api (An example of a generic interface for cryptographic things, not in the scope of lib-rand, but it'd be good to not make things hard to fit into an api like this.)

Summary of research from other languages:

Structures and functions commonly appearing

Distributions:

Very common/important:

• Normal
• Exponential
• Uniform (discrete and continuous)
• Gamma (many distributions are special cases/functions of this, e.g. Chi^2, F, t, beta, even uniform.)

Variations on implementation seen

Pitfalls and hazards associated with each variant

Relationship to other libraries and/or abstract interfaces

4. Module writing

• WIP: https://github.com/huonw/rust-rand
• Pull request: link to bug

Additional implementation notes

• Rng should take &mut self, instead of forcing the use of mutable fields
• Generating many random numbers at once: methods that fill vectors, or iterators?
• note