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

Greg Ewing greg.ewing at canterbury.ac.nz
Mon Aug 17 04:13:01 CEST 2009

Scott David Daniels wrote:

No, I don't really need MT. The others would be fine. I'd love further details.

The one I've been working with is due to Pierre L'Ecuyer [1] and is known as MRG32k3a. It's a combined multiple recursive linear congruential generator with 6 words of state. The formulas are

 r1[i] = (a12 * r1[i-2] + a13 * r1[i-3]) % m1
 r2[i] = (a21 * r2[i-1] + a23 * r2[i-3]) % m2
 r[i] = (r1[i] - r2[i]) * m1

where

 m1 = 2**32 - 209
 m2 = 2**32 - 22835

 a12 = 1403580
 a13 = -810728
 a21 = 527612
 a23 = -1370589

If you consider the state to be made up of two 3-word state vectors, then there are two 3x3 matrices which map a given state onto the next state. So to jump ahead n steps in the sequence, you raise these matrices to the power of n.

I've attached some code implementing this generator together with the jumping-ahead. (Sorry it's in C++, I hadn't discovered Python when I wrote it.)

[1] Pierre L'Ecuyer, Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, Operations Research v47 no1 Jan-Feb 1999 http://www.iro.umontreal.ca/~lecuyer/myftp/papers/combmrg2.ps

-- Greg -------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: cmr_random_generator.C URL: <http://mail.python.org/pipermail/python-dev/attachments/20090817/13e73d1d/attachment.txt> -------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: cmr_random_generator.H URL: <http://mail.python.org/pipermail/python-dev/attachments/20090817/13e73d1d/attachment.asc>

More information about the Python-Dev mailing list