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

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

$$LCG(27817185604309,16555425264690,0,1).$$

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

L'Ecuyer cLCGs

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.