internal state of python random module

Question

import random
random.seed(234)
state = random.getstate()

The result state is a tuple:

(3, (.... many long integers...),  None)

What does this exactly mean? I know I can save the state and use random.setstate(state) to recover the internal state for any random number generator used in this module. But I dont know what are these values in the state mean. The official document doesn't say any detail about it. I guess it might mean the parameters for determine a random state.

Answer 1

The algorithm used since Python 2.3 is the Mersenne Twister. The docs note that the state is implementation specific. So I wouldn't rely on any particular details of the state unless you really need to.

The Mersenne Twister starts by initializing an array of integers, using the seed. Here's a helpful (slightly edited) Python code snippet from the Wikipedia article on Mersenne Twister:

    state = [0] * 624
    state[0] = seed
    for i in range(1, 624):
        state[i] = int(
            0xFFFFFFFF & (1812433253 * (state[i - 1] ^ state[i - 1] >> 30) + i)
        )

Note this is unsigned bit arithmetic. This is the algorithm used to generate the state, as can be seen in the CPython source code.

The CPython code sets 624 as the last element of the state to use as an index variable, so the state array actually has 625 elements versus 624 in the Wikipedia snippet above. The "twist" operation uses this index variable.

When I compared the results of using the Python Wikipedia code with random module, I didn't get the same 624 integers. I think this is probably a combination of the Python code not doing the same arithmetic as the C code and the seed being manipulated by the C code. I'll take a look when I have more time, hopefully.