[Python-Dev] Time for a change of random number generator?

[Tim Peters]

[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 ;-)