[Python-Dev] random number generator state

[Greg Ewing]

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>