Mersenne Twister
The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士).
[1][2] Its name derives from the choice of a Mersenne prime as its period length.
The Mersenne Twister was designed specifically to rectify most of the flaws found in older PRNGs.
There is another implementation (with five variants[3]) that uses a 64-bit word length, MT19937-64; it generates a different sequence.
of w-bit integers of period P is said to be k-distributed to v-bit accuracy if the following holds.
For a w-bit word length, the Mersenne Twister generates integers in the range
The Mersenne Twister algorithm is based on a matrix linear recurrence over a finite binary field
The algorithm is a twisted generalised feedback shift register[4] (twisted GFSR, or TGFSR) of rational normal form (TGFSR(R)), with state bit reflection and tempering.
through a simple recurrence relation, and then output numbers of the form
The twist transformation A is defined in rational normal form as:
As like TGFSR(R), the Mersenne Twister is cascaded with a tempering transform to compensate for the reduced dimensionality of equidistribution (because of the choice of A being in the rational normal form).
for T an invertible matrix, and therefore the analysis of characteristic polynomial mentioned below still holds.
As with A, we choose a tempering transform to be easily computable, and so do not actually construct T itself.
The first and last transforms are added in order to improve lower-bit equidistribution.
As a result, the d is occasionally omitted from the algorithm description, since the bitwise and with d in that case has no effect.
The state needed for a Mersenne Twister implementation is an array of n values of w bits each.
To initialize the array, a w-bit seed value is used to supply
being the characteristic polynomial of The twist transformation improves the classical GFSR with the following key properties: CryptMT is a stream cipher and cryptographically secure pseudorandom number generator which uses Mersenne Twister internally.
[6][7] It was developed by Matsumoto and Nishimura alongside Mariko Hagita and Mutsuo Saito.
[6] Unlike Mersenne Twister or its other derivatives, CryptMT is patented.
MTGP is a variant of Mersenne Twister optimised for graphics processing units published by Mutsuo Saito and Makoto Matsumoto.
[8] The basic linear recurrence operations are extended from MT and parameters are chosen to allow many threads to compute the recursion in parallel, while sharing their state space to reduce memory load.
The paper claims improved equidistribution over MT and performance on an old (2008-era) GPU (Nvidia GTX260 with 192 cores) of 4.7 ms for 5×107 random 32-bit integers.
[11] TinyMT is a variant of Mersenne Twister, proposed by Saito and Matsumoto in 2011.
, far shorter than the original, so it is only recommended by the authors in cases where memory is at a premium.
Advantages: Disadvantages: The Mersenne Twister is used as default PRNG by the following software: It is also available in Apache Commons,[47] in the standard C++ library (since C++11),[48][49] and in Mathematica.
[54] The Mersenne Twister is similarly one of the PRNGs in SAS: the other generators are older and deprecated.
[57] Marsaglia's xorshift generators and variants are the fastest in the class of LFSRs.
-Linear Generators with Mersenne Prime Period") are completely optimized in terms of the k-distribution properties.
[59] The ACORN family (published 1989) is another k-distributed PRNG, which shows similar computational speed to MT, and better statistical properties as it satisfies all the current (2019) TestU01 criteria; when used with appropriate choices of parameters, ACORN can have arbitrarily long period and precision.
