Jump to content

Mersenne Twister

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 86.138.249.106 (talk) at 21:58, 27 June 2006 (→Pseudocode). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士). It provides for fast generation of very high quality pseudorandom numbers, having been designed specifically to rectify many of the flaws found in older algorithms.

There are at least two common variants of the algorithm, differing only in the size of the Mersenne primes used. The newer and more commonly used one is the Mersenne Twister MT 19937.

Advantages

MT 19937 has the following desirable properties:

  1. It was designed to have a colossal period of 219937 − 1 (the creators of the algorithm proved this property). This period explains the origin of the name: it is a Mersenne prime, and some of the guarantees of the algorithm depend on internal use of Mersenne primes. In practice, there is little reason to use larger ones. [citation needed]
  2. It has a very high order of dimensional equidistribution (see linear congruential generator). Note that this means, by default, that there is negligible serial correlation between successive values in the output sequence.
  3. It is faster than all but the most statistically unsound generators.
  4. It passes numerous tests for statistical randomness, including the stringent Diehard tests.

How the algorithm works

The algorithm itself is a twisted generalised feedback shift register or TGFSR for short. The "twist" is a transformation which assures equidistribution of the generated numbers in 623 dimensions (linear congruential generators can at best manage reasonable distribution in 5 dimensions).

Unlike Blum Blum Shub, the algorithm in its native form is not suitable for cryptography. Observing a sufficient number of iterates allows one to predict all future iterates. Combining the Mersenne twister with a hash cures this problem but slows down generation.

For many other applications, however, the Mersenne twister is fast becoming the random number generator of choice.

Pseudocode

The following generates uniformly 32 bit integers in the range [0, 2^32 - 1] with the MT19937 algorithm: 

 // Create a length 624 array to store the state of the generator
 var int[0..623] MT
 // Initialise the generator from a seed
 function initialiseGenerator ( 32-bit int seed ) {
     MT[0] := seed
     for i from 1 to 623 { // loop over each other element
         MT[i] := last_32bits_of((69069 * MT[i-1]) + 1)
     }
 }

 // Generate an array of 624 untempered numbers
 function generateNumbers() {
     for i from 0 to 622 {
         y := 32nd_bit_of(MT[i]) + last_31bits_of(MT[i+1])
         if y even {
             MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y))
         } else if y odd {
             MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
         }
     }
     y := 32nd_bit_of(MT[623]) + last_31bits_of(MT[0])
     if y even {
         MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y))
     } else if y odd {
         MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
     }
 }
 
 // Extract a tempered pseudorandom number based on the i-th value
 function extractNumber(int i) {
     y := MT[i]
     y := y bitwise_xor (right_shift_by_11_bits(y))
     y := y bitwise_xor (left_shift_by_7_bits(y) bitwise_and (2636928640))
     y := y bitwise_xor (left_shift_by_15_bits(y) bitwise_and (4022730752))
     y := y bitwise_xor (right_shift_by_18_bits(y))
     return y
 }

Reference

  • M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Mersenne_Twister&oldid=60912850"