mersenne_twister.cpp

class MTRand {
public:
    typedef unsigned int u32;
    MTRand(u32 s=5489) :p(0) {
        for(int i=0;i<n;i++) state[i]=0;
        seed(s);
    }
    void seed(u32 s) {
        state[0] = s & 0xFFFFFFFFUL;
        for (int i = 1; i < n; ++i) {
            state[i] = 1812433253UL * (state[i - 1] ^ (state[i - 1] >> 30)) + i;
            state[i] &= 0xFFFFFFFFUL;
        }
        p = n;
    }
    u32 operator()() {
        if (p == n) gen_state(); u32 x = state[p++];
        x ^= (x >> 11); x^=(x<<7)&0x9D2C5680UL;  x ^= (x << 15) & 0xEFC60000UL;
        return x ^ (x >> 18);
    }
	u32 operator()(u32 max) { return operator()(0, max - 1); }
    u32 operator()(u32 min, u32 max) {
        u32 m=max-min;
        u32 u=m|(m>>1); u|=u>>2; u|=u>>4; u|=u>>8; u|=u>>16;
        u32 i; do { i=operator()() & u; } while(i>m); return i+min;
    }

private:
    enum { n = 624, m = 397 };u32 state[n]; int p;
    u32 twiddle(u32 u, u32 v)
        { return (((u&0x80000000UL)|(v&0x7FFFFFFFUL)) >> 1)^ ((v & 1UL)?0x9908B0DFUL:0x0UL); }
     void gen_state() {
        for (int i = 0; i < (n - m); ++i)
            state[i] = state[i + m] ^ twiddle(state[i], state[i + 1]);
        for (int i = n - m; i < (n - 1); ++i)
            state[i] = state[i + m - n] ^ twiddle(state[i], state[i + 1]);
        state[n - 1] = state[m - 1] ^ twiddle(state[n - 1], state[0]);
        p = 0;
    }
};