[Python-Dev] a note in random.shuffle.__doc__ ...
tim.peters at gmail.com
Sun Jun 11 05:10:42 CEST 2006
> 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
2**19937 - 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 2**19937 - 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