-
Notifications
You must be signed in to change notification settings - Fork 0
Lib rand
Generating random numbers, and sampling from random distributions.
- Proposed editor: Huon Wilson (@huonw)
- Date proposed: date of proposal
- Link: link to email
-
Standard: standard - link to docs - ...
-
Standard: standard - link to docs - ...
-
Technique: Generating random bits/numbers (i.e
u32
oru64
) - 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 - 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
-
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?
-
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.) - 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/
- Most languages/implementations just multiply the random int by
- Language: C++11 - http://www.cplusplus.com/reference/random/
- Language: Python - http://docs.python.org/3.3/library/random.html
- 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
- Language: Julia (also a statistical language) - https://github.com/JuliaStats/Distributions.jl
- Language: D - http://dlang.org/phobos/std_random.html (no support for sampling from distributions other than uniform, but many RNGs)
- Language: Go - http://golang.org/pkg/math/rand/
- Language: Erlang - https://mail.mozilla.org/pipermail/rust-dev/2013-April/003881.html
- 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
- Library: Numpy/Scipy - http://docs.scipy.org/doc/numpy/reference/routines.random.html - http://docs.scipy.org/doc/scipy/reference/stats.html
- Library: Boost - http://www.boost.org/doc/libs/1_53_0/doc/html/boost_random/reference.html
- Library: RandomKit
- Library: Tina's Random Number Generator Library - Includes many distributions, also support for/discussion about parallel RNGs.
- 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.)
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.)
- WIP: https://github.com/huonw/rust-rand
- Pull request: link to bug
-
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