Inverting Mersenne Twister's final transform
The Mersenne twister RNG 'tempers' its output using an invertible transformation:
unsigned int temper(unsigned int x)
{
x ^= (x >> 11);
x ^= (x << 7) & 0x9D2C5680;
x ^= (x << 15) & 0xEFC60000;
x ^= (x >> 18);
return x;
}
The inversion function is:
unsigned int detemper(unsigned int x)
{
x ^= (x >> 18);
x ^= (x << 15) & 0xEFC60000;
x ^= (x << 7) & 0x1680;
x ^= (x << 7) & 0xC4000;
x ^= (x << 7) & 0xD200000;
x ^= (x << 7) & 0x90000000;
x ^= (x >> 11) & 0xFFC00000;
x ^= (x >> 11) & 0x3FF800;
x ^= (x >> 11) & 0x7FF;
return x;
}
This inversion has been confirmed correct with exhaustive search.
This is more a note to my future self than anything else; I'm cleaning out my ~/projects directory, and I can either publish this somewhere or check it into revision control (well, actually the contents of this blog are also in revision control, but no matter).
Posted in programming at 2009/07/21 16:40; 0 comments
< Isn't Autoconf Supposed To Be, Well, Automatic? | Speeding up Serpent: SIMD Edition >