Previous: , Up: random generators   [Index]


49.8.5 Combined multiple recursive generator

This is a combined multiple recursive generator. The algorithm was derived from:16

P. L’Ecuyer. “Combined Multiple Recursive Random Number Generators”. Operations Research, 44, 5 (1996), 816–822.

the following bindings are exported by the (vicare crypto randomisations cmrg) library.

Function: make-random-source/cmrg

Build and return a new randomness source using a CMRG generator.

The state returned by random-source-state-ref is a Scheme vector of length 7, whose first value is the symbol random-source-state/cmrg. The other values are integers representable with 32 bits.

The random-source-seed! function for this generator, must be applied to a numbers maker returning integers representable with 32 bits.

The algorithm

The sequence is:

N = (X0 - Y0) mod m1

where the two underlying generators X and Y are:

X0 = (A1 X1 + A2 X2 + A3 X3) mod M1
Y0 = (B1 Y1 + B2 X2 + B3 Y3) mod M2

with coefficients:

A1 = 0       A2 = 63308   A3 = -183326
B1 = 86098   B2 = 0       B3 = -539608

and moduli:

M1 = 2^31 - 1       = 2147483647
M2 = 2^31 - 2000169 = 2145483479

According to the paper the initial values for X must lie in the range 0 <= X < M1 and the initial values for Y must lie in the range 0 <= Y < M2, with at least one non–zero value. (vicare crypto randomisations cmrg) initialises the generator with:

X1 = 7   X2 = 17   X3 = 47
Y1 = 3   Y2 = 13   Y3 = 43

and the seeding procedure implemented by the randomness source (through random-source-seed!) will extract random numbers from the given generator until it is 0 < X < M1 and 0 < Y < M2.


Footnotes

(16)

It is available from L’Ecuyer’s home page (URL last verified Tue Jul 14, 2009):

http://www.iro.umontreal.ca/~lecuyer/myftp/papers/combmrg.ps
ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/combmrg.ps

Previous: , Up: random generators   [Index]