From Wikipedia, the free encyclopedia
Pseudorandom number generator
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 created specifically to address most of the flaws found in earlier PRNGs.
The most commonly used version of the Mersenne Twister algorithm is based on the Mersenne prime 2 19937 − 1 {\displaystyle 2^{19937}-1} . The standard implementation of that, MT19937, uses a 32-bit word length. There is another implementation (with five variants[3]) that uses a 64-bit word length, MT19937-64; it generates a different sequence.
A pseudorandom sequence x i {\displaystyle x_{i}} 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 [ 0 , 2 w − 1 ] {\displaystyle [0,2^{w}-1]} .
The Mersenne Twister algorithm is based on a matrix linear recurrence over a finite binary field F 2 {\displaystyle {\textbf {F}}_{2}} . 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. The basic idea is to define a series x i {\displaystyle x_{i}} through a simple recurrence relation, and then output numbers of the form x i T {\displaystyle x_{i}^{T}} , where T is an invertible F 2 {\displaystyle {\textbf {F}}_{2}} -matrix called a tempering matrix.
The general algorithm is characterized by the following quantities:
with the restriction that 2 n w − r − 1 {\displaystyle 2^{nw-r}-1} is a Mersenne prime. This choice simplifies the primitivity test and k-distribution test needed in the parameter search.
The series x {\displaystyle x} is defined as a series of w-bit quantities with the recurrence relation:
where ∣ {\displaystyle \mid } denotes concatenation of bit vectors (with upper bits on the left), ⊕ {\displaystyle \oplus } the bitwise exclusive or (XOR), x k u {\displaystyle x_{k}^{u}} means the upper w − r bits of x k {\displaystyle x_{k}} , and x k + 1 l {\displaystyle x_{k+1}^{l}} means the lower r bits of x k + 1 {\displaystyle x_{k+1}} .
The subscripts may all be offset by -n
where now the LHS, x k {\displaystyle x_{k}} , is the next generated value in the series in terms of values generated in the past, which are on the RHS.
The twist transformation A is defined in rational normal form as: A = ( 0 I w − 1 a w − 1 ( a w − 2 , … , a 0 ) ) {\displaystyle A={\begin{pmatrix}0&I_{w-1}\\a_{w-1}&(a_{w-2},\ldots ,a_{0})\end{pmatrix}}} with I w − 1 {\displaystyle I_{w-1}} as the ( w − 1 ) ( w − 1 ) {\displaystyle (w-1)(w-1)} identity matrix. The rational normal form has the benefit that multiplication by A can be efficiently expressed as: (remember that here matrix multiplication is being done in F 2 {\displaystyle {\textbf {F}}_{2}} , and therefore bitwise XOR takes the place of addition) x A = { x ≫ 1 x 0 = 0 ( x ≫ 1 ) ⊕ a x 0 = 1 {\displaystyle {\boldsymbol {x}}A={\begin{cases}{\boldsymbol {x}}\gg 1&x_{0}=0\\({\boldsymbol {x}}\gg 1)\oplus {\boldsymbol {a}}&x_{0}=1\end{cases}}} where x 0 {\displaystyle x_{0}} is the lowest order bit of x {\displaystyle x} .
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). Note that this is equivalent to using the matrix A where A = T − 1 ∗ A T {\displaystyle A=T^{-1}*AT} 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. This tempering is defined in the case of Mersenne Twister as
where x {\displaystyle x} is the next value from the series, y {\displaystyle y} is a temporary intermediate value, and z {\displaystyle z} is the value returned from the algorithm, with ≪ {\displaystyle \ll } and ≫ {\displaystyle \gg } as the bitwise left and right shifts, and & {\displaystyle \&} as the bitwise AND. The first and last transforms are added in order to improve lower-bit equidistribution. From the property of TGFSR, s + t ≥ ⌊ w 2 ⌋ − 1 {\displaystyle s+t\geq \left\lfloor {\frac {w}{2}}\right\rfloor -1} is required to reach the upper bound of equidistribution for the upper bits.
The coefficients for MT19937 are:
( w , n , m , r ) = ( 32 , 624 , 397 , 31 ) a = 9908B0DF 16 ( u , d ) = ( 11 , FFFFFFFF 16 ) ( s , b ) = ( 7 , 9D2C5680 16 ) ( t , c ) = ( 15 , EFC60000 16 ) l = 18 {\displaystyle {\begin{aligned}(w,n,m,r)&=(32,624,397,31)\\a&={\textrm {9908B0DF}}_{16}\\(u,d)&=(11,{\textrm {FFFFFFFF}}_{16})\\(s,b)&=(7,{\textrm {9D2C5680}}_{16})\\(t,c)&=(15,{\textrm {EFC60000}}_{16})\\l&=18\\\end{aligned}}}
Note that 32-bit implementations of the Mersenne Twister generally have d = FFFFFFFF16. 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 coefficients for MT19937-64 are:[5]
( w , n , m , r ) = ( 64 , 312 , 156 , 31 ) a = B5026F5AA96619E9 16 ( u , d ) = ( 29 , 5555555555555555 16 ) ( s , b ) = ( 17 , 71D67FFFEDA60000 16 ) ( t , c ) = ( 37 , FFF7EEE000000000 16 ) l = 43 {\displaystyle {\begin{aligned}(w,n,m,r)=(64,312,156,31)\\a={\textrm {B5026F5AA96619E9}}_{16}\\(u,d)=(29,{\textrm {5555555555555555}}_{16})\\(s,b)=(17,{\textrm {71D67FFFEDA60000}}_{16})\\(t,c)=(37,{\textrm {FFF7EEE000000000}}_{16})\\l=43\\\end{aligned}}}
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 x 0 {\displaystyle x_{0}} through x n − 1 {\displaystyle x_{n-1}} by setting x 0 {\displaystyle x_{0}} to the seed value and thereafter setting
for i {\displaystyle i} from 1 {\displaystyle 1} to n − 1 {\displaystyle n-1} .
#include <stdint.h>
#define n 624
#define m 397
#define w 32
#define r 31
#define UMASK (0xffffffffUL << r)
#define LMASK (0xffffffffUL >> (w-r))
#define a 0x9908b0dfUL
#define u 11
#define s 7
#define t 15
#define l 18
#define b 0x9d2c5680UL
#define c 0xefc60000UL
#define f 1812433253UL
typedef struct
{
uint32_t state_array[n]; // the array for the state vector
int state_index; // index into state vector array, 0 <= state_index <= n-1 always
} mt_state;
void initialize_state(mt_state* state, uint32_t seed)
{
uint32_t* state_array = &(state->state_array[0]);
state_array[0] = seed; // suggested initial seed = 19650218UL
for (int i=1; i<n; i++)
{
seed = f * (seed ^ (seed >> (w-2))) + i; // Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier.
state_array[i] = seed;
}
state->state_index = 0;
}
uint32_t random_uint32(mt_state* state)
{
uint32_t* state_array = &(state->state_array[0]);
int k = state->state_index; // point to current state location
// 0 <= state_index <= n-1 always
// int k = k - n; // point to state n iterations before
// if (k < 0) k += n; // modulo n circular indexing
// the previous 2 lines actually do nothing
// for illustration only
int j = k - (n-1); // point to state n-1 iterations before
if (j < 0) j += n; // modulo n circular indexing
uint32_t x = (state_array[k] & UMASK) | (state_array[j] & LMASK);
uint32_t xA = x >> 1;
if (x & 0x00000001UL) xA ^= a;
j = k - (n-m); // point to state n-m iterations before
if (j < 0) j += n; // modulo n circular indexing
x = state_array[j] ^ xA; // compute next value in the state
state_array[k++] = x; // update new state value
if (k >= n) k = 0; // modulo n circular indexing
state->state_index = k;
uint32_t y = x ^ (x >> u); // tempering
y = y ^ ((y << s) & b);
y = y ^ ((y << t) & c);
uint32_t z = y ^ (y >> l);
return z;
}
Comparison with classical GFSR[edit]
In order to achieve the 2 n w − r − 1 {\displaystyle 2^{nw-r}-1} theoretical upper limit of the period in a TGFSR, ϕ B ( t ) {\displaystyle \phi _{B}(t)} must be a primitive polynomial, ϕ B ( t ) {\displaystyle \phi _{B}(t)} 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. It has been submitted to the eSTREAM project of the eCRYPT network.[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.
The SFMT (SIMD-oriented Fast Mersenne Twister) is a variant of Mersenne Twister, introduced in 2006,[9] designed to be fast when it runs on 128-bit SIMD.
Intel SSE2 and PowerPC AltiVec are supported by SFMT. It is also used for games with the Cell BE in the PlayStation 3.[11]
TinyMT is a variant of Mersenne Twister, proposed by Saito and Matsumoto in 2011.[12] TinyMT uses just 127 bits of state space, a significant decrease compared to the original's 2.5 KiB of state. However, it has a period of 2 127 − 1 {\displaystyle 2^{127}-1} , 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.[50] Add-on implementations are provided in many program libraries, including the Boost C++ Libraries,[51] the CUDA Library,[52] and the NAG Numerical Library.[53]
The Mersenne Twister is one of two PRNGs in SPSS: the other generator is kept only for compatibility with older programs, and the Mersenne Twister is stated to be "more reliable".[54] The Mersenne Twister is similarly one of the PRNGs in SAS: the other generators are older and deprecated.[55] The Mersenne Twister is the default PRNG in Stata, the other one is KISS, for compatibility with older versions of Stata.[56]
An alternative generator, WELL ("Well Equidistributed Long-period Linear"), offers quicker recovery, and equal randomness, and nearly equal speed.[57]
Marsaglia's xorshift generators and variants are the fastest in the class of LFSRs.[58]
64-bit MELGs ("64-bit Maximally Equidistributed F 2 {\displaystyle {\textbf {F}}_{2}} -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.
The PCG family is a more modern long-period generator, with better cache locality, and less detectable bias using modern analysis methods.[60]
A subsequent paper, published in the year 2000, gave five additional forms of the Mersenne Twister with period 2^19937-1. All five were designed to be implemented with 64-bit arithmetic instead of 32-bit arithmetic.
Built-in Function: rand
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4