[Python-Dev] a note in random.shuffle.__doc__ ...

[Tim Peters]

[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
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().