Multiple Recursive Generator: MRG

**Quote**[144, p. 2]: *As computational power gets cheaper,
increasingly long sequences of random numbers are used in applications.
Generators with longer periods and which are more reliable are then
necessary.
One alternative is the class of multiple recursive generators (MRGs)
*(ref. are given in the paper)* based on the higher order recursion:
*

Proposed by Tausworthe [220] for modulus 2 and by Knuth [126] for arbitrary prime modulus, MRGs have been studied extensively by Grube in his PhD-thesis [81,82]. For a statistical study of different PRNGs where the MRGs showed the best results, see [219].

Similar to LCGs, the set of all overlapping -tuples of values
forms a lattice structure in (for details see
[49,80,82,148]).
**Quote:**[49] *MRGs of order behave in like
LCGs in * .
The lattice structure may be analyzed by the spectral test as well.
Recent computer searches
for good parameters can be found in [114,117,144].
Further theoretical properties of MRGs are discussed in [113].
Upper bounds for the spectral test for certain MRG implementations
(implementations with many vanishing parameters exhibit bad bounds)
are given in [115].

Grube-DieterMRGs

In [81] Grube proposed the following parameters for :

3 | 4 | 5 | 6 | 7 | 8 | |||||

1 | 241639237 | 0.935 | 0.548 | 0.787 | 0.717 | 0.569 | 0.556 | 0.732 | ||

2 | 337190270 | 268152554 | 0.613 | 0.677 | 0.579 | 0.716 | 0.655 | 0.667 | ||

3 | 518175991 | 510332243 | 71324449 | 0.818 | 0.653 | 0.584 | 0.737 | 0.491 |

For spectral test results of MRG 2,3 see [143]. Further MRGs for and the corresponding lattice analysis are given in Dieter [48,49]. The table below contains some examples from [49]. Empirical and theoretical results of some of the MRGs contained in the latter papers (including the first MRG below and the third MRG above) are given in [85].

4 | 5 | 6 | 7 | 8 | |||||

2 | 318558375 | 202725360 | 0.765 | 0.665 | 0.628 | 0.664 | 0.587 | 0.617 | |

2 | 524824023 | 488461699 | 0.778 | 0.591 | 0.571 | 0.770 | 0.510 | 0.653 | |

3 | 312017767 | 325891459 | 391624983 | 0.851 | 0.693 | 0.597 | 0.719 | 0.561 | |

3 | 388425559 | 227651891 | 5412951 | 0.829 | 0.621 | 0.529 | 0.682 | 0.720 |

L'EcuyerMRGs

Using a spectral test- and a lattice test (Beyer ratio) search, L'Ecuyer et. al. [144] obtained the MRGs with parameters given in the table below. Implementations in Pascal and C are contained in the latter paper.

Parameters for and obtained by an earlier search of L'Ecuyer et. al. are published in [143]. For empirical results of one of these generators see [85]. MRG no. 8 in the table below is implemented as a part of a combined MRG in the SPRNG library [23].

2 | 2 | 3 | 3 | 3 | |||

1498809829 | 46325 | 65338 | 1476728729 | 2021422057 | |||

1160990996 | 1084587 | 0 | 0 | 1826992351 | |||

64636 | 1155643113 | 1977753457 | |||||

4 | 4 | 5 | 6 | 7 | 7 | 7 | |

2001982722 | 64886 | 107374182 | 177786 | 1975938786 | 2109532706 | 1071 064 | |

1412284257 | 0 | 0 | 0 | 875540239 | 0 | 0 | |

1155380217 | 0 | 0 | 0 | 433188390 | 0 | 0 | |

1668339922 | 65322 | 0 | 0 | 451413575 | 0 | 0 | |

104480 | 0 | 1658907683 | 0 | 0 | |||

64654 | 1513645334 | 0 | 0 | ||||

1428037821 | 1651737654 | 2113 664 | |||||

2 | 2 | 3 | 2 | 5 | |||

65069701955467 | 11138366 | 11209406 | 2975962250 | 2949964090 | |||

123597951337197 | 11808124 | 0 | 2909704450 | 0 | |||

11721934 | 0 | ||||||

0 | |||||||

2946716567 |

Recently, Pierre L'Ecuyer studied combined MRGs [135,139,138]. Empirical results of such generators are given in [140,137,146,145].