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:

$$x_n := (a_1 x_{n-1} + \cdots + a_k x_{n-k}) \bmod m.$$

For a given prime modulus $m$, such generators can reach a period length of $m^k-1$ and the good ones have much better structural properties than the simple MLCGs with the same modulus, while being almost as fast and easy to implement [132].

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 $s$-tuples of values $u_n = x_n / m$ forms a lattice structure in $[0,1[^s$ (for details see [49,80,82,148]). Quote:[49] MRGs of order $k$ behave in ${\bf R}^{s k}$ like LCGs in ${\bf R}^s$ . 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 $a_i$ exhibit bad bounds) are given in [115].

Grube-DieterMRGs

In [81] Grube proposed the following parameters for $m = 2^{31}-1$:

$k$	$a_1$	$a_2$	$a_3$	$s = 2$	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 $k = 2,3$ 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].

$k$	$a_1$	$a_2$	$a_3$	$s=3$	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 $1\le k \le 7$ and $m \in \{ 2^{15} - 19, 2^{31}-1 \}$ 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].

$m$	$2^{31}-1$	$2^{31}-1$	$2^{31}-1$	$2^{31}-1$	$2^{31}-1$
$k$	2	2	3	3	3
$a_1$	1498809829	46325	65338	1476728729	2021422057
$a_2$	1160990996	1084587	0	0	1826992351
$a_3$			64636	1155643113	1977753457
$m$	$2^{31}-1$	$2^{31}-1$	$2^{31}-1$	$2^{31}-1$	$2^{31}-19$	$2^{31}-19$	$2^{31}-19$
$k$	4	4	5	6	7	7	7
$a_1$	2001982722	64886	107374182	177786	1975938786	2109532706	1071 064
$a_2$	1412284257	0	0	0	875540239	0	0
$a_3$	1155380217	0	0	0	433188390	0	0
$a_4$	1668339922	65322	0	0	451413575	0	0
$a_5$			104480	0	1658907683	0	0
$a_6$				64654	1513645334	0	0
$a_7$					1428037821	1651737654	2113 664
$m$	$2^{47}-115$		$2^{47}-115$	$2^{47}-115$	$2^{63}-25$	$2^{63}-711$
$k$	2		2	3	2	5
$a_1$	65069701955467		11138366	11209406	2975962250	2949964090
$a_2$	123597951337197		11808124	0	2909704450	0
$a_3$				11721934		0
$a_4$						0
$a_5$						2946716567

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