next up previous contents
Next: Combined LCGs: cLCG Up: A collection of classical Previous: Parallel LCGs   Contents

Subsections


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:

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

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].


next up previous contents
Next: Combined LCGs: cLCG Up: A collection of classical Previous: Parallel LCGs   Contents
Karl Entacher 2000-06-16