choice of A being in the rational normal form). Note that this is equivalent to using the matrix A where 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 tempering is defined in the case of Mersenne Twister as where is the next value from the series, is a temporary intermediate value, and is the value returned from the algorithm, with and as the bitwise left and right shifts, and as the bitwise AND. The first and last transforms are added in order to improve lower-bit equidistribution. From the property of TGFSR, is required to reach the upper bound of equidistribution for the upper bits. The coefficients for MT19937 are: 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: Initialization 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 through by setting to the seed value and thereafter setting for from to . The first value the algorithm then generates is based on , not on . The constant f forms another parameter to the generator, though not part of the algorithm proper. The value for f for MT19937 is 1812433253. The value for f for MT19937-64 is 6364136223846793005. Comparison with classical GFSR In order to achieve the theoretical upper limit of the period in a TGFSR, must be a primitive polynomial, being the characteristic polynomial of The twist transformation improves the classical GFSR with the following key properties: The period reaches the theoretical upper limit (except if initialized with 0) Equidistribution in n dimensions (e.g. linear congruential generators can at best manage reasonable distribution in five dimensions) Pseudocode The following pseudocode implements the general Mersenne Twister algorithm. The constants w, n, m, r, a, u, d, s, b, t, c, l, and f are as in the algorithm description above. It is assumed that int represents a type sufficient to hold values with w bits: // Create a length n array to store the state of the