mersenne_twister.py

"""
    Mersenne Twister
    ----------------
    Generates high quality pseudo random integers with a long period.
    Used as the default random number generator for several
    languages (including Python).

    For a more technical overview, see the wikipedia entry.

    Pseudocode: http://en.wikipedia.org/wiki/Mersenne_twister
"""


class MersenneTwister:
    def __init__(self):
        self.state = []
        self.index = 0

    def seed(self, seed):
        """
        Initialize generator.

        :param seed: An integer value to seed the generator with
        """
        self.state = []
        self.index = 0
        self.state.append(seed)
        for i in range(1, 624):
            n = (0x6c078965 * (self.state[i-1] ^ (self.state[i-1] >> 30)) + i)
            n &= 0xffffffff
            self.state.append(n)

    def randint(self):
        """
        Extracts a random number.

        :rtype: A random integer
        """
        if self.index == 0:
            self.generate()

        y = self.state[self.index]
        y ^= y >> 11
        y ^= (y << 7) & 0x9d2c5680
        y ^= (y << 15) & 0xefc60000
        y ^= y >> 18

        self.index = (self.index + 1) % 624
        return y

    def generate(self):
        """
        Generates 624 random numbers and stores in the state list.

        """
        for i in range(624):
            n = self.state[i] & 0x80000000
            n += self.state[(i+1) % 624] & 0x7fffffff
            self.state[i] = self.state[(i+397) % 624] ^ (n >> 1)
            if n % 2 != 0:
                self.state[i] ^= 0x9908b0df