Lib rand

Generating random numbers, and sampling from random distributions.

1. Announcement to mailing list

• Proposed editor: your name
• 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"
   • WELL
   • SIMD-oriented Fast Mersenne Twister (SFMT)
     • dSFMT is used by Julia, and possibly Erlang - 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
   • Not crypto quality, fast
   • "Tables of maximally equidistributed combined LSFR generators" L'Ecuyer 1999 (includes a 64 bit variant) - 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)
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 - NIST - Add a new make target "check-rngs" with a testsuite?
5. Technique: sampling from distributions - Inverse transform sampling (fully general) - Ziggurat algorithm (distributions with decreasing density functions) - Box-Muller transform and Marsaglia polar method (normal distribution, both are almost certainly inferior to the ziggurat algorithm) - "A simple method for generating gamma variables" Marsaglia & Tsang 2000

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
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

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

• Pull request: link to bug

Additional implementation notes

• note
• note
• note