The default random-number generator in Python, R, PHP, Ruby and Excel for two decades. It keeps a 624-word state, twists it, and tempers each output with shifts and masks — giving a period of 219937−1 (a Mersenne prime) and even spread in up to 623 dimensions. Its tempering is pure bitwise, which I-13 has; only its seeding hits a familiar wall.
THE TECHNIQUE twist the state, temper the output
Hold 624 32-bit words. To refill, twist: each word is recombined with the next and one 397 ahead, with a shift and a conditional xor. Each value drawn is then tempered — y ^= y>>11; y ^= (y<<7)&M1; y ^= (y<<15)&M2; y ^= y>>18 — to scramble its bits. Draw some (default seed 5489): live demo
HISTORY & CREDIT long, fast, and predictable
The word “random” in a dozen languages points here — to a generator that is unbreakable trivially predictable once you have watched it. cited
1997 · Makoto Matsumoto & Takuji Nishimura publish the Mersenne Twister — a twisted generalised feedback shift register whose period is the Mersenne prime 219937−1. the strength · 623-dimensional equidistribution to 32-bit accuracy: successive outputs are evenly spread in very high dimension, which is why it passed the statistical tests of its day. the weakness · it is not cryptographically secure — observe 624 consecutive outputs and you can invert the tempering, recover the whole state, and predict everything after. Never seed a keystream with it. the successors · PCG (O’Neill, 2014) and xoshiro (Blackman-Vigna) are smaller, faster, and better-distributed — the modern defaults.
A generator can be enormous and even and still be an open book. long ≠ unpredictable
RECOMMEND FOR I-13 tempering runs; seeding hits the 32-bit multiply
The output tempering is pure bitwise — the shifts and masks I-13 integrated (darts 001/004/029) — and it runs exactly:
$ i13 run temper.i13 # y ^ y>>11 ^ (y<<7 & M1) ^ (y<<15 & M2) ^ y>>18
out = 729696813 # temper(305419896), bit-exact vs the reference
Recommend: the generator core runs — the 624-word state is a bounded array, the twist and temper are bitwise xor/shift/and, all landed. The one wall is the seeding: mt[i] = 1812433253 * (…) + i needs a 32-bit multiply that wraps mod 232, which overflows f64’s exact range — the same wrap-around-multiply wall the de Bruijn bit-scan (dart 060) surfaced. Twist + temper are no-walls; only the init multiply waits on a fixed-width modular multiply. Note: so I-13 can run the Twister with a pre-seeded state today; it just cannot yet compute the seed expansion exactly.