# MINSTD
[](https://crates.io/crates/minstd)
[](https://unlicense.org)
[](https://blog.rust-lang.org/2021/10/21/Rust-1.56.0.html)
[](https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html)
[](https://docs.rust-embedded.org/book/intro/no-std.html)
[](https://deps.rs/repo/gitlab/hsn10/minstd)
[](https://docs.rs/minstd)
[](https://crates.io/crates/minstd/versions)
[](https://github.com/XAMPPRocky/tokei)
This multiplicative congruential pseudo random number generator is called
"The minimal standard generator" or MCG16807.
First described in 1988 Park and Miller paper
[Random number generators: Good ones are hard to find](https://www.cems.uwe.ac.uk/~irjohnso/coursenotes/ufeen8-15-m/p1192-parkmiller.pdf).
Generator _modulus m_ = 2^31-1 is Mersene prime M31.
The _multiplier a_ = 7^5 = 16807 was first suggested by
Lewis, Goodman and Miller in 1969.
Multiplicative congruential [generators of this form](https://en.wikipedia.org/wiki/Lehmer_random_number_generator)
are ascribed to _D. H. Lehmer_ and they are know as Lehmer random number generators.
First described by Hutchinson and independently by Downham and Roberts.
Generator was later criticized by [Marsaglia and Sullivan](https://www.firstpr.com.au/dsp/rand31/p105-crawford.pdf)
(1993). While it is still in use today
(in particular: in [CarbonLib](https://macintoshgarden.org/apps/carbonlib),
in Matlab as [mcg16807](https://www.mathworks.com/help/matlab/ref/randstream.html),
FreeBSD 5 as [rand()](https://github.com/freebsd/freebsd-src/blob/releng/5.0/lib/libc/stdlib/rand.c)
and in C++11 as [function minstd_rand0](https://en.cppreference.com/w/cpp/numeric/random))
Park, Miller and Stockmeyer "officially" since July 1990 advocate
_a = 48271_ multiplier.
Updated version performs much better in [Spectral test](https://en.wikipedia.org/wiki/Spectral_test)
where performs very well up to 6th dimension.
## Minimalistic code
This code have _no dependencies_ and is not using standard library.
Can be used in [embedded](https://docs.rust-embedded.org/book/) or
[webasm](https://rustwasm.github.io/docs/book/) environments.
## MINSTD / 1990 version
Multiplier 48271
https://oeis.org/A221556
## MINSTD0 / 1988 version
Multiplier 16807
https://oeis.org/A096550
## Spectral test
|16807 |0.3375|0.4412 |0.5752| 0.7361| 0.6454 | 0.5711|0.6096|
|48271 |0.8960|0.8269 |0.8506| 0.7332| 0.8078 | 0.5865|0.4364|
|69621 |0.7836|0.9205 |0.8516| 0.7318| 0.7667 | 0.6628|0.7845|
Value 0.75 or higher is considered good enough to pass spectral
test.
Because too many multipliers pass *0.75 test* for MCG M31 generator,
researches changed limit to 0.8 while doing
[An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus 2(31)-1](https://archive.org/embed/DTIC_ADA143085)
and found 207 optimal multipliers while first 5 are much better than the rest.
## MCG31
Uses multiplier *1132489760* recommended in paper
[MATHEMATICS OF COMPUTATION Volume 68, Number 225, January 1999](https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf).
This multiplier have good spectral results in higher dimensions.
|1132489760 1583458089|0.72771|0.61996|0.61996|
|784588716 163490618|0.65885|0.65388|0.65388|
Second alternative multiplier is generating the same sequence, just reversed.
Used in [Arm HPC](https://developer.arm.com/documentation/101004/2504/Open-Random-Number-Generation-Reference-Guide/Modules/Basic-random-number-generator-constants/VSL-BRNG-MCG31?lang=en)
and [Intel VSL](https://www.intel.com/content/www/us/en/docs/onemkl/developer-reference-vector-statistics-notes/2021-1/basic-random-number-generators.html).
## License
This is free and unencumbered software released into the public domain.
This code can be used under terms of [CC0-1.0](https://creativecommons.org/publicdomain/zero/1.0/) or
the [Unlicense](https://unlicense.org).
