k-distribution A pseudorandom sequence of w-bit integers of period P is said to be k-distributed to v-bit accuracy if the following holds. Let truncv(x) denote the number formed by the leading v bits of x, and consider P of the k v-bit vectors . Then each of the possible combinations of bits occurs the same number of times in a period, except for the all-zero combination that occurs once less often. Algorithmic detail 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 (twisted GFSR, or TGFSR) of rational normal form (TGFSR(R)), with state bit reflection and tempering. The basic idea is to define a series through a simple recurrence relation, and then output numbers of the form , where T is an invertible -matrix called a tempering matrix. The general algorithm is characterized by the following quantities (some of these explanations make sense only after reading the rest of the algorithm): w: word size (in number of bits) n: degree of recurrence m: middle word, an offset used in the recurrence relation defining the series , r: separation point of one word, or the number of bits of the lower bitmask, a: coefficients of the rational normal form twist matrix b, c: TGFSR(R) tempering bitmasks s, t: TGFSR(R) tempering bit shifts u, d, l: additional Mersenne Twister tempering bit shifts/masks with the restriction that is a Mersenne prime. This choice simplifies the primitivity test and k-distribution test that are needed in the parameter search. The series is defined as a series of w-bit quantities with the recurrence relation: where denotes concatenation of bit vectors (with upper bits on the left), the bitwise exclusive or (XOR), means the upper bits of , and means the lower r bits of . The twist transformation A is defined in rational normal form as:with as the 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 , and therefore bitwise XOR takes the place of addition)where is the lowest order bit of . As like TGFSR(R), the Mersenne Twister is cascaded with a tempering transform to compensate for the reduced dimensionality of equidistribution (because of the