next up previous contents
Next: Further ``Linear'' Methods and Up: A collection of classical Previous: Multiple Recursive Generator: MRG   Contents

Subsections


Combined LCGs: cLCG

Combining different streams $(u_n^{\scriptscriptstyle (j)})_{n\ge0}$, $1\le j
\le r$, of pseudorandom numbers into a new stream $(u_n)_{n\ge 0}$, $u_n \equiv u_n^{\scriptscriptstyle (1)}+\ldots +
u_n^{\scriptscriptstyle (r)} \!\!\pmod{1}$ yields an easy way to achieve long periods while keeping the computational costs of generating the numbers low by choosing suitable parameters for each underlying generator. For references and an overview of this technique and its difficulties see [134, Sect. 9] and [186, Sect. 4.2]. Different combination methods (combined generators, composite congruential generators, compound generators, $\ldots$ ) are given in [30,51,73,107,131,149,199,210,211]. Quote[134]: Theoretical results in [20,164] (see also [85, p. 70]) appear to support the view (at first glance) that combined generators should have better statistical behavior in general than their individual components. However, as explained in [132], applying those theoretical results to ``deterministic'' generators is a somewhat shaky reasoning. Combination can conceivably worsen things. Nevertheless, empirical results strongly support combinations [133,164].

However, the more theoretical properties of a combined generator are known, the less undesired side-effects are possible.

In contrast to hybrid combinations, the combination of (multiplicative) LCGs only yields the advantage that the underlying structure of $s$-dimensional overlapping tuples is known. This is due to the fact that cLCGs are equivalent to single LCGs with large moduli [85,149,235].

Combined LCGs provide an easy way to partition their output sequences into disjoint parallel streams by varying the seeds [84,85]. From the equivalence to LCGs, it follows that splitting a cLCG needs certain precautions as well [43]. Using a modified spectral test, MacLaren [161] has suggested a method to test the independence of parallel streams for cLCGs (and LCGs). The latter paper is the basis for the combined LCGs implemented in the Nag PVM Library.

A combination of multiplicative LCGs was first suggested by Wichmann and Hill [235].



Wichmann and Hill cLCG


\includegraphics[width=5.0cm]{eps/wichi2.eps}


Wichmann and Hill [235] combined three multiplicative LCGs:

LCG $s = 2$ 3 4 5 6 7 7
$LCG(30269,171,0,1)$ 0.9147 0.183 0.4082 0.6605 0.8212 0.4813 0.5507
$LCG(30307,172,0,1)$ 0.9195 0.6228 0.7039 0.7854 0.785 0.7014 0.584
$LCG(30323,170,0,1)$ 0.9085 0.6821 0.4639 0.7507 0.6049 0.7415 0.584

Zeisl (1986) [235] completed that this generator is equivalent to

\begin{displaymath}LCG(27817185604309,16555425264690,0,1).\end{displaymath}

For implementations see the StatLib server and [199, RAN7]. Empirical studies and further remarks on this generator are contained in [214].



L'Ecuyer cLCGs


\includegraphics[width=5.0cm]{eps/lecC1.eps}

In order to implement combined LCGs, the following ``good-lattice'' LCGs are suggested in [131]. The zoom above stems from $LCG(32504802982957,30890646900944,0,1)$ which is equivalent to the combined generators using LCG 9, 12 and 13 (observe the ``weak'' lattice in dimension 2).

no. $m$ $a\backslash s$ 2 3 4 5 6 7 8
1 $2^{31}-1$ 39373 0.791 0.755 0.787 0.758 0.754 0.779 0.560
2 2147483563 40014 0.803 0.836 0.788 0.828 0.808 0.474 0.663
3 2147483399 40692 0.817 0.818 0.805 0.891 0.819 0.474 0.663
4 2147482811 41546 0.834 0.787 0.811 0.808 0.821 0.709 0.692
5 2147482801 42024 0.844 0.811 0.857 0.783 0.810 0.558 0.740
6 2147482739 45742 0.919 0.851 0.783 0.820 0.799 0.322 0.449
7 32749 162 0.833 0.796 0.710 0.658 0.763 0.505 0.578
8 32749 219 0.930 0.793 0.726 0.718 0.763 0.733 0.721
9 32363 157 0.812 0.851 0.827 0.782 0.788 0.584 0.669
10 32143 160 0.830 0.754 0.807 0.728 0.777 0.675 0.611
11 32119 172 0.893 0.719 0.735 0.776 0.740 0.653 0.511
12 31727 146 0.763 0.722 0.727 0.758 0.729 0.676 0.547
13 31657 142 0.743 0.762 0.824 0.785 0.779 0.655 0.698
Results of a battery of empirical tests are given for generator 3 and for two combined generators using generator 2 and 3 (32bit) and generator 9, 12 and 13 (16bit) (see also [118]). Portable implementations are provided as well. Empirical results and implementations of the combined generator RANECU using LCG 2 and 3 are published in [26,28,45,107,147,160,188,191,190,200] ([147,188] support splitting facilities). RANECU is further implemented within the software FINDER [191,190], in the simulation tool GEANT(3.21) and in [25, MATHLIB] [206] [199, RAN24].

An implementation using a combination of four LCGs (the parameters are given in the table below) which provides improved structural properties is given in [142].

no. $m$ $a\backslash s$ 2 3 4 5 6 7 8
14 2147483647 45991 0.924 0.819 0.790 0.719 0.716 0.761 0.698
15 2147483543 207707 0.208 0.831 0.615 0.499 0.690 0.646 0.670
16 2147483423 138556 0.321 0.913 0.770 0.652 0.580 0.729 0.610
17 2147483323 49689 0.994 0.777 0.508 0.776 0.613 0.676 0.638



NAG PVM Library (G05AAFP) - cLCGs

The NAG PVM (parallel virtual machine) Library Chapter G05 contains parameters for 273 combined multiplicative LCGs, four LCGs combined respectively (for example the first combination consists of $LCG(16770647,125,0,1)$, $LCG(16770643,117,0,1)$, $LCG(16770623,127,0,1)$ and $LCG(16770617,126,0,1)$). The different generators are used to produce ``independent'' parallel PRNGs. This approach is based on the paper of MacLaren [161]. The ``independence'' is tested with a modified spectral test.


next up previous contents
Next: Further ``Linear'' Methods and Up: A collection of classical Previous: Multiple Recursive Generator: MRG   Contents
Karl Entacher 2000-06-16