| msg158406 - (view) |
Author: Dave Reid (Dave.Reid) |
Date: 2012-04-16 09:09 |
| 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. |
|
|
| msg158408 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) *  |
Date: 2012-04-16 10:57 |
| Indeed, jumpahead may have problems on non-32-bit platforms. The proposed patch fixes it. Porting to Python 3 is not required. |
|
|
| msg158417 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2012-04-16 12:01 |
| Thanks for the report and patch. I've investigate and load a fix this week. |
|
|
| msg158476 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-04-16 16:00 |
| 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 */ |
|
|
| msg158699 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2012-04-19 05:42 |
| This needs a patch. |
|
|
| msg158700 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-04-19 06:54 |
| 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.) |
|
|
| msg158701 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-04-19 07:16 |
| 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). |
|
|
| msg158958 - (view) |
Author: Antoine Pitrou (pitrou) * |
Date: 2012-04-22 12:54 |
| The patch should probably come with an unit test. |
|
|
| msg158959 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-04-22 12:56 |
| Patch with unit test. :-) |
|
|
| msg158961 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-04-22 12:56 |
| Dang. Patch now attached. |
|
|
| msg160263 - (view) |
Author: Antoine Pitrou (pitrou) * |
Date: 2012-05-09 08:47 |
| In test_random, you should use assertLess so that the offending value is displayed on failure. |
|
|
| msg160268 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-05-09 10:16 |
| Done. |
|
|
| msg162128 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-06-02 08:32 |
| 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. |
|
|
| msg162829 - (view) |
Author: Serhiy Storchaka (serhiy.storchaka) * |
Date: 2012-06-14 21:20 |
| > 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. |
|
|
| msg163438 - (view) |
Author: Mark Dickinson (mark.dickinson) * |
Date: 2012-06-22 17:04 |
| Raymond, can this patch be applied? |
|
|
| msg163894 - (view) |
Author: Raymond Hettinger (rhettinger) * |
Date: 2012-06-25 05:19 |
| 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. |
|
|
| msg164393 - (view) |
Author: Roundup Robot (python-dev)  |
Date: 2012-06-30 16:19 |
| 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 |
|
|