[Python-Dev] random number generator state (original) (raw)

Mark Dickinson dickinsm at gmail.com
Sun Aug 16 02:00:42 CEST 2009

On Sat, Aug 15, 2009 at 8:54 PM, Scott David Daniels<Scott.Daniels at acm.org> wrote:

[...] input to .setstate: old, new-short, and new-long.  In trying to get this to work, I found what might be a bug: code says  mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */ but probably should be:  mt[0] |= 0x80000000UL; /* MSB is 1; assuring non-zero initial array */

I'm 92.3% sure that this isn't a bug. For one thing, that line comes directly from the authors' code[1], so if it's a bug then it's a bug in the original code, dating from 2002; this seems unlikely, given how widely used and (presumably) well-scrutinized MT is.

For a more technical justification, the Mersenne Twister is based on a linear transformation of a 19937-dimensional vector space over F2, so its state naturally consists of 19937 bits of information, which is 623 words plus one additional bit. In this implementation, that extra bit is the top bit of the first word; the other 31 bits of that first word shouldn't really be regarded as part of the state proper. If you examine the genrand_int32 function in _randommodule.c, you'll see that the low 31 bits of mt[0] play no role in updating the state; i.e., their value doesn't affect the new state. So using mt[0] |= 0x80000000UL instead of mt[0] = 0x80000000UL during initialization should make no difference to the resulting stream of random numbers (with the possible exception of the first random number generated).

[1] http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c

Mark

More information about the Python-Dev mailing list