[Python-Dev] random number generator state
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