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).