[Python-Dev] Time for a change of random number generator? (original) (raw)

Tim Peters tim.peters at gmail.com
Thu Feb 11 23:15:00 EST 2016

[Greg Ewing <greg.ewing at canterbury.ac.nz>]

The Mersenne Twister is no longer regarded as quite state-of-the art because it can get into states that produce long sequences that are not very random.

There is a variation on MT called WELL that has better properties in this regard. Does anyone think it would be a good idea to replace MT with WELL as Python's default rng?

I don't think so, because I've seen no groundswell of discontent about the Twister among Python users. Perhaps I'm missing some? Changes are disruptive and people argue about RNGs with religious zeal, so I favor making a change in this area only when it's compelling. It was compelling to move away from Wichmann-Hill when the Twister was introduced: WH was waaaaaay behind the state of the art at the time, its limitations were causing real problems, and there was near-universal adoption of the Twister around the world. The Twister was a game changer.

When the time comes for a change, I'd be more inclined to (as Robert Kern already said) look at PCG and Random123. Like the Twister, WELL requires massive internal state, and fails the same kinds of randomnesss tests (while the suggested alternatives fail none to date). WELL does escape "zeroland" faster, but still much slower than PCG or Random123 (which appear to have no systematic attractors). The alternatives require much smaller state, and at least PCG much simpler code.

Note that the seeding function used by Python doesn't take the user-supplied seed as-is (only setstate does): it runs rounds of pseudo-random bit dispersion, to make it highly unlikely that an initial state with lots of zeroes is produced. While the Twister escapes zeroland very slowly, the flip side is that it also transitions to zeroland very slowly. It's quite possible that nobody has ever fallen into such a state (short of contriving to via setstate). Falling into zeroland was a very real problem in the Twister's very early days, which is why its authors added the bit-dispersal code to the seeding function. Python was wise to wait until they did.

It's prudent to wait for someone else to find the early surprises in PCG and Random123 too ;-)

More information about the Python-Dev mailing list