[Python-Dev] a note in random.shuffle.doc ... (original) (raw)

Tim Peters tim.peters at gmail.com
Sun Jun 11 05:10:42 CEST 2006

[Greg Ewing]

But isn't the problem with the Twister that for *some initial states* the period could be much shorter than the theoretical maximum?

Or is the probability of getting such an initial state too small to worry about?

The Twister's state is held in a vector of 624 32-bit words. 31 of the bits aren't actually used, and the number of meaningful state bits is actually 624 * 32 - 31 = 19937.

There are exactly 2 orbits in the state space under the state transformation operation (STO):

  1. A trivial orbit of length 1, consisting of the state in which all meaningful bits are 0. That's a fixed point for the STO. There are no other fixed points.

  2. All not-entirely-0 states are in the other orbit, of length 219937 - 1. All not-0 states are reachable from all other not-0 states, and you get back to the non-zero state you start from for the first time after exactly 219937 - 1 iterations of the STO.

So as long as you don't start with the all-0 state, you're in the second orbit, and see the advertised period (2**19937 - 1).

From Python code, it's impossible to get the all-0 state. All Python-visible initialization methods guarantee there's at least one bit set in the meaningful bits of the state vector, so the probability of not seeing a period of 2**19937 - 1 from Python is exactly 0.

Hmm. Well, there is a way to screw yourself here, but you have to work at it: you can force the all-0 state by hand-crafting the right input to random.setstate().

More information about the Python-Dev mailing list