MINSTD

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.

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 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 (1993). While it is still in use today (in particular: in CarbonLib, in Matlab as mcg16807, FreeBSD 5 as rand() and in C++11 as function minstd_rand0) Park, Miller and Stockmeyer "officially" since July 1990 advocate a = 48271 multiplier.

Updated version performs much better in Spectral test where performs very well up to 6th dimension.

MINSTD / 1990 version

Multiplier 48271

https://oeis.org/A221556

MINSTD0 / 1988 version

Multiplier 16807

https://oeis.org/A096550

Spectral tests

Spectral tests of popular small, easy to remember, multipliers. Larger multipliers give better results and on current 32/64 bit systems they do not have any additional computation cost.

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 and found 207 optimal multipliers while first 5 are much better than the rest.

S1, S2, S3 values for best performing multipliers for m = M31

MCG31 / 1999 version

Use of multiplier 1132489760 is recommended in paper MATHEMATICS OF COMPUTATION Volume 68, Number 225, January 1999. This multiplier have good spectral results in higher (16, 32) dimensions. Results in low dimensions are less good compared to previous table.

Paper recommends two multipliers for MCG with M31 modulo:

Second alternative multiplier is generating the same but reversed sequence without difference in spectral test. Its modular multiplicative inverse modulo M31.

Used in Arm HPC and Intel VSL.

Custom MCG M31 Generator

You can create Multiplicative congruential generator with your custom multiplier and M31 modulo. Choose best performing multiplier in your desired dimension. You will get better results than using stock multipliers.

Functions verify_multiplier and verify_period will help you test if your choosen multiplier is capable of producing full period generator.

Function inverse_multiplier computes the modular inverse of a given multiplier a modulo M31. You can use this function to test if your multiplier is inverse of some well known multiplier.

Minimalistic code

This library have no runtime dependencies and is not using standard library. Can be used in embedded or webasm environments.

License

This is free and unencumbered software released into the public domain.

This code can be used under terms of CC0-1.0 or the Unlicense.