homepage

A particular combination of seed and jumpahead calls seems to force the MT generator into a state where it produces a random variate that is outside the range 0-1. Problem looks like it might be in _randommodule.c:genrand_int32, which produces a value > 0xffffffff for the given state, but I don't understand the generator well enough to debug any further.
The attached test case produces 1.58809998297 as the 2nd variate in Python 2.7 and 1.35540900431 as the 23rd variate in Python 2.7.3. The problem occurs on both Linux (CentOS 6) and Mac OSX (10.6.8), both 64-bit.

Indeed, jumpahead may have problems on non-32-bit platforms. The proposed patch fixes it. Porting to Python 3 is not required.

Thanks for the report and patch. I've investigate and load a fix this week.

Patch looks good to me.
There's one other subtle bug in random_jumpahead, which is that it's not guaranteed that the resulting state is nonzero. The way to fix this is to add a line like the one near the end of the 'init_by_array' function.
mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */

This needs a patch.

Here's a modification of Serhiy's patch that assures that the new state is nonzero.
(Just to clarify the nonzero requirement: the MT state is formed from bit 31 of mt[0] together with all the bits of mt[i], 1 <= i < 624. At least one of these 19937 bits must be nonzero.)

The latest patch has the disadvantage that it'll often change the behaviour of jumpahead for people on 32-bit platforms, which may lead to unnecessary breakage.
Here's a better version that only fixes mt[0] in the unlikely (but possible) event that mt[1] through mt[623] are all zero. That should mean that users on 32-bit machines who are depending on jumpahead being reproducible won't notice (unless they're very unlucky indeed).

The patch should probably come with an unit test.

Patch with unit test. :-)

Dang. Patch now attached.

In test_random, you should use assertLess so that the offending value is displayed on failure.

Done.

Responding to a comment from Serhiy on Rietveld:
> Modules/_randommodule.c:442: mt[0] = 0x80000000UL;
> mt[0] |= 0x80000000UL (according to the comment)?
The = 0x80000000UL was intentional. The low-order 31 bits of mt[0] don't form part of the state of the Mersenne Twister: the resulting random stream isn't affected by their values. So all we have to do is make sure that bit 31 is set. It's the same code that's used in init_by_array earlier in _randommodule.c.

> The = 0x80000000UL was intentional. The low-order 31 bits of mt[0] don't form part of the state of the Mersenne Twister: the resulting random stream isn't affected by their values.
Thanks, I have no more questions.

Raymond, can this patch be applied?

The patch is fine but would be a bit better if the two loop passes were merged and if the "tmp" variable were renamed to something like "nonzero" or somesuch.

New changeset 6df0b4ed8617 by Mark Dickinson in branch '2.7':
Closes #14591: Random.jumpahead could produce an invalid MT state on 64-bit machines.
http://hg.python.org/cpython/rev/6df0b4ed8617