Mersenne Twister

Description

The Mersenne Twister is a pseudorandom number generator designed by Makoto Matsumoto and Takuji Nishimura. Its standard version, MT19937, works with $32$-bit words. Its state is an array of $624$ words, that is $19\,968$ bits, of which $19\,937$ bits are effective. The transition function is linear over the field with two elements $\F_2$. It combines three words of the array by shifts, masks and exclusive or, in a twisted generalised feedback shift register recurrence. The output function applies a fixed invertible linear map, the tempering, to the newest word. It fits the definition of a generator: the state space is finite, and the transition and output are fixed maps. The seed determines the initial array. Its period is $2^{19937} - 1$, which is a Mersenne prime; this is where the name comes from. Its outputs are $623$-dimensionally equidistributed to $32$-bit accuracy. That is, over a full period every $623$-tuple of consecutive $32$-bit outputs occurs equally often, except that the all-zero tuple occurs once less.