Parallel LCGs

An obvious way to get parallel streams of PRNs is to partition a sequence of a given pseudorandom number generator into suitable subsequences. This can be achieved in different ways.

In Subsection , we study the well known ``leap-frog'' technique where the original sequence of a generator is split into lagged subsequences with a given lag $k$. Whereas a single stream of a LCG performs well in practice, due to good spectral test results, the quality of lagged subsequences of such a stream may be worsen considerably. Hence whenever lagged subsequences occur in a particular simulation problem these sequences have to be tested as well.

In [65] we showed how to analyze correlations within and between lagged subsequences with arbitrary step sizes $k$ generated from LCGs with power-of-two- and prime moduli. In Subsection we recall basic concepts from [65] and apply them to several examples of LCGs.

By varying the initial seed $x_0$ one easily may partition a sequence of a LCG into consecutive blocks of a given length. An extensive discussion of this method for LCGs with respect to parallelization was given by DeMatteis and Pagnutti [39] (see also [38,40,41,42,43,44,53]). It turns out that only reduced fractions of sequences produced by LCGs can safely be used because of the well known long-range correlations which may cause high correlations between parallel streams. Critical lengths of consecutive blocks for several LCGs are given e.g. for RANF [38,40,42], L'Ecuyer LCG 3 [38], MINSTD [38], Super-Duper and RANDU [42]. Using the spectral test it is possible to exhibit these long-range correlations in a stronger way. Whereas the latter authors studied correlations between pairs of processors only, the spectral test offers an easy tool to analyze correlations between an arbitrary number of parallel streams, see Subsection .

Sometimes it is recommended, to use separate generators to produce parallel streams of random numbers e.g. see [8]. In Subsection we give a simple example of three LCGs with perfect spectral test results but strong correlations within the parallel streams obtained from these generators.

Our subsequence analyses of LCGs use classical notions from linear random number generation. A more general analysis of lagged subsequences with arbitrary lacunary indices from multiple recursive generators has been discussed and performed in [136,148].

Spectral Test and Lagged Subsequences

With the ``leap-frog'' technique [16,27,54,132,134] the output ${\bf x} := (x_n)_{n\ge 0}$ of a LCG is partitioned into lagged subsequences of the form

$${\bf\omega}_k^{\scriptscriptstyle (j)}:= (x_{k n + j})_{n\ge 0},\quad k \ge 2,\quad 0 \le j \le k-1.$$ (1)

Consider a mixed linear congruential generator $LCG(m,a,b,0)$ with maximal period $\rho$. For this generator, the subsequence () is also produced by (see also [134,203])

$$LCG\left ( m, a^k\!\!\pmod m, \textstyle{ b\cdot \frac{a^... ... \frac{a^j-1}{a-1}}\!\!\pmod m \right ), \;\; 0 \le j \le k-1.$$ (2)

For the multiplicative full-period $LCG(m, a, 0, 1)$, the corresponding LCG which produces the subsequence () is given by

$$LCG(m, a^k\!\!\pmod m, 0, a^j\!\!\pmod m ),\quad 0 \le j \le k-1.$$ (3)

Note that the period of these subsequences equals $\rho_k = \rho /gcd(k,\rho)$.

Even if one chooses subsequences with maximal period $\rho_k=\rho$, these sequences can be of inferior quality. This can be easily shown by the spectral test. The table below gives some examples. G_k denotes the LCG which generates a full-period subsequence $(x_{k n})_{n\ge 0}$ of generator G. Further results can be found in [62,63].

LCG	Sect.	$s = 2$	3	4	5	6	7	8
ANSIC_25		0.0822	0.7978	0.6059	0.7767	0.6327	0.5936	0.6096
MINSTD_25		0.5967	0.0782	0.4427	0.5401	0.478	0.5036	0.56
BCSLIB_45		0.7494	0.7596	0.0766	0.2122	0.4544	0.7216	0.659
Super-Duper_59		0.0910	0.6132	0.5992	0.7485	0.6342	0.5902	0.6648
Super-Duper_81		0.0594	0.6492	0.8133	0.6886	0.6249	0.6729	0.6771
Super-Duper_99		0.0202	0.2071	0.6	0.2933	0.418	0.4603	0.635
Super-Duper_135		0.6758	0.6143	0.5708	0.0999	0.1281	0.2016	0.2781
Super-Duper_153		0.1729	0.0567	0.2795	0.7636	0.5872	0.536	0.4071
FISH2_29		0.0903	0.5806	0.286	0.615	0.7007	0.5815	0.5641
FISH7_65		0.0968	0.4785	0.5557	0.7437	0.4426	0.6962	0.7433
FISH7_105		0.926	0.00945	0.0500	0.1367	0.2608	0.4103	0.566
FISH8_3		0.7092	0.0806	0.4301	0.5704	0.5862	0.6166	0.6307
FISH15_23		0.2562	0.0600	0.0114	0.0462	0.1275	0.2031	0.2077
NAG_13		0.0875	0.7036	0.2369	0.7165	0.6532	0.6219	0.5455
DERIVE_33		0.4475	0.0591	0.1459	0.3601	0.3438	0.559	0.6495
LCG.1_17		0.0811	0.7742	0.4712	0.5983	0.5382	0.552	0.5512
LCG.1_83		0.0919	0.5215	0.6726	0.4304	0.6951	0.619	0.7282
LCG.1_97		0.6802	0.0410	0.2317	0.57	0.6822	0.5278	0.5883
LCG.3_33		0.0088	0.3013	0.3845	0.6992	0.6632	0.6371	0.5961

Note that FISH15_23, FISH7_105 exhibit normalized spectral test results worse than RANDU. The zoom into the 3-dimensional unit cube above stems from FISH15_23. The second graphics shows the 15 hyperplanes that cover all three-dimensional overlapping tuples generated by FISH7_105. A parallel application using LCG.1 is given in [159].

If a subsequence-LCG does not have full period, the underlying lattice structure obviously can be of reduced quality as well. In the graphics below we demonstrate this behavior with some zooms into the unit square which contain all overlapping vectors $(u_n,u_{n+1})_{n\ge 0}$ generated by the by the LCGs: MINSTD_77, SIMSCRIPT_78 and RANF_36 . Compare the zooms in the Sections , and .

MINSTD_77		SIMSCRIPT_78		RANF_36

But how to assess non-full period subsequences with the spectral test? As an example, we consider ``the reminder of the good old days, the early 1950s'', the LCG with multiplier $a = 5^{15}$ (BCSLIB, URN12, CDC Computers, SIMULA)⁷, which already was analyzed by Coveyou and MacPherson [36] with the spectral test. In particular we analyze certain non-full period subsequences of $GEN = LCG(2^\beta,5^{15},0,1)$ which, especially for $\beta = 48$, is studied in different parallel settings (including the leap-frog method) in [16].

Quote[16, p. 451]: This 'leapfrog' algorithm was subjected to an analysis of correlation, exactly as was done for the Lehmer tree algorithm. The choices $a = 5^{15}$, $c = 0$, and $m = 2^{48}$ were again made and 50000 numbers were generated in each parallel sequence for analysis by linear regression. From 8 to 512 parallel processes were examined. No significant correlations were found between pairs of processes.

Let's make a more detailed study of these ``8 to 512 parallel processes''. In the subsections below we first recall some basic lattice theory of LCGs and then study the quality reduction of the lattice structure generated by lagged subsequences with step sizes $k = 2^l$, $l\ge 1$ of $GEN$. Note that this analysis applies to arbitrary linear congruential pseudorandom number generator with power-of-two moduli as well.

Lattice Analysis

For the three standard parametrization schemes of LCGs [184, p. 169] (see also [8,73,201]) the set of vectors { ${\bf u}_n^{\scriptscriptstyle (s)}$ $= (u_n,\ldots,u_{n+s-1})$ : $n\ge 0 \}$ forms a grid structure. In the case of $GEN$, a multiplicative LCG with power-of-two modulus $m = 2^\beta$ and $a\equiv 5\!\!\pmod 8$, the set of all vectors ${\bf u}_n^{\scriptscriptstyle (s)}$ is equal to the intersection of the $s$-dimensional unit cube $[0,1[^s$ with the shifted lattice

$$\frac{1}{4} {\bf b}_1 + L_s (a,2^{\beta - 2}) \quad \mbox{wi... ...=1}^s \nu_i\cdot{\bf b}_i, \quad \nu_i \in {\bf Z} \right \},$$ (4)

and lattice basis ${\cal B} = \{{\bf b}_1, \ldots, {\bf b}_s \}$, defined by the vectors

$${\bf b}_1 = (1,a,\ldots,a^{s-1})/2^{\beta - 2}, \quad {\bf b}_2 = (0,1,0,\ldots,0), \ldots , {\bf b}_s = (0,0,\ldots,0,1).$$

For the proof see [184, Thm. 7.6] or [47,163,201]. The spectral test measures the coarseness of lattice $L_s (a,2^{\beta - 2})$. The calculation of this test is realized using the dual lattice of $L_s (a,2^{\beta - 2})$, since the maximal distance of adjacent hyperplanes $d_s$ is equal to one over the length of the shortest vector of the dual lattice pointed out by Dieter [47]. Moreover, the $L_1$-norm minus one, of the shortest vector gives an upper bound of the number of hyperplanes $n_s$ on which all $s$-tuples ${\bf u}_n^{\scriptscriptstyle (s)}$ lie [47], see also [73, Sect. 7.8]. An efficient implementation of the spectral test for multiple recursive generators which supports subsequence analyses is given in [148]. Our calculation of this test uses a Mathematica implementation of the Fincke-Pohst algorithm for finding the shortest vector in a lattice by Wilberd van der Kallen., University of Utrecht, Netherlands.

We now describe the lattice structure obtained by subsequences () with step sizes $k = 2^l$, $l\ge 1$. Recall the basic recursion of $GEN$: $x_n \equiv a \cdot x_{n-1}\pmod m$, $m = 2^\beta$, and w.l.o.g. $x_0 = 1$. From [201, Prop. 1] (see also [73, p. 599]) we get

$$x_n = 4\cdot x_n^* + 1 \quad \mbox{where} \quad x_n^* \equiv... ...t x_{n-1}^* + (a-1)/4\!\!\pmod{2^{\beta - 2}},\;\; x_0^* = 0,$$ (5)

which, by the way, yields the period $\rho = 2^{\beta - 2}$ of $GEN$. Using equation (4) in [126, p. 12], see also [7, p. 944], it follows that for $k = 2^l, l\ge 1$,

$$x_{k n + j}^* = y_j + k\cdot z_n,\quad n, z_n\in\{ 0,\ldots,2^{\beta -l-2}-1\},$$ (6)

and $y_j \equiv a \cdot y_{j-1} + (a-1)/4\!\!\pmod k$, $y_0 = 0$. Let $j$ be fixed, therefore the set $\{ x_{k n + j} : n \ge 0 \}$ equals $\{ 4\cdot k\cdot u + v : u = 0,\ldots ,2^{\beta - l -2} -1$, $v = 4 y_j + 1 \}$. The latter result and property (), applied in exactly the same calculation as in [47, Sect. 4] yields that the set of all overlapping vectors ${\bf u}_{k n + j}^{\scriptscriptstyle (s)}$ consists of all points of the intersection of the $s$-dimensional unit cube $[0,1[^s$ with the shifted lattice $v\cdot {\bf b}_1 / 2^{l+2} + L_s(c, 2^{46-l})$ with modified lattice vector ${\bf b}_1 = (1,c,\ldots,c^{s-1})/2^{46-l}$, $c = a^k\!\!\pmod m$.

Therefore, the spectral test of the $2^l$-subsequences has to be calculated using the latter vector ${\bf b}_1$ (with constant $1/2^{46-l}$ !).

Note that if one uses constant $1/2^{46}$ for the calculation, this would give the spectral test for the union of all subsequence-grids. This is not the appropriate way to asses the subsequence structure. For example, the GEN-subsequence with step size $k = 2^8$ yields the weak spectral test $S_5 = 0.03502$ whereas for the union of the subsequence-grids $S_5 = 0.4662$.

We applied the normalized spectral test $S_s$, $2 \le s \le 8$, to $GEN$-subsequences with step sizes $k = 2^l$, $1 \le l \le 9$. As can be seen from the tables below, with increasing $l$, the quality of the subsequence-lattices strongly decreases. The tables report the results for $GEN$ with moduli $2^\beta$, $\beta = 32$, 35, 48. Perhaps there are no ``correlations'' between pairs of parallel streams, as stated above, but the quality of each stream is very poor for $l \ge 6$.

$\beta = 32$
$s$	$l = 0$	1	2	3	4	5	6	7	8	9
2	0.8215	0.6721	0.8523	0.3516	0.8074	0.3232	0.6026	0.8581	0.6962	0.9306
3	0.6130	0.3172	0.6175	0.8089	0.6096	0.8078	0.5735	0.3437	0.0541	0.0170
4	0.4117	0.6233	0.2177	0.5172	0.5141	0.6538	0.0588	0.0699	0.0743	0.0442
5	0.3466	0.7097	0.2594	0.6708	0.7395	0.2124	0.0922	0.1059	0.0942	0.0884
6	0.6277	0.6898	0.4727	0.7297	0.4068	0.2283	0.1531	0.1719	0.1220	0.1370
7	0.6686	0.6095	0.5495	0.7214	0.2995	0.3307	0.1690	0.1866	0.1682	0.1857
8	0.4003	0.6781	0.6060	0.4915	0.3933	0.2808	0.2165	0.2361	0.2102	0.2292

$\beta = 35$
$s$	$l = 0$	1	2	3	4	5	6	7	8	9
2	0.5809	0.4897	0.6027	0.8904	0.7587	0.9141	0.8522	0.3773	0.8814	0.6853
3	0.4145	0.8614	0.7296	0.8089	0.6924	0.6897	0.8175	0.6827	0.21651	0.0341
4	0.8004	0.7402	0.6691	0.7393	0.3793	0.6151	0.2795	0.0415	0.0494	0.0526
5	0.6401	0.6601	0.4333	0.8432	0.6032	0.1401	0.1609	0.0699	0.0803	0.0714
6	0.6951	0.6746	0.5526	0.5160	0.4315	0.1614	0.1812	0.1216	0.1364	0.0969
7	0.6379	0.6570	0.5627	0.6143	0.3855	0.2457	0.2293	0.1387	0.15309	0.1380
8	0.7473	0.5229	0.7831	0.5852	0.4863	0.2165	0.1928	0.1821	0.1985	0.1768

$\beta = 48$
$s$	$l = 0$	1	2	3	4	5	6	7	8	9
2	0.9599	0.2776	0.5677	0.2635	0.6914	0.8752	0.9076	0.4763	0.6009	0.8353
3	0.5761	0.7166	0.7645	0.6931	0.2755	0.6031	0.7606	0.2767	0.7722	0.6447
4	0.5178	0.7922	0.5831	0.8606	0.6442	0.5691	0.4973	0.7558	0.6598	0.0988
5	0.4799	0.6529	0.6434	0.3833	0.3943	0.5396	0.2998	0.2439	0.0350	0.0402
6	0.6001	0.4908	0.5149	0.6316	0.3332	0.6300	0.1211	0.1359	0.0508	0.0571
7	0.6956	0.7539	0.6962	0.5439	0.6390	0.3896	0.1297	0.1432	0.0913	0.1008
8	0.6715	0.6452	0.6179	0.5873	0.6679	0.3292	0.1875	0.1524	0.0910	0.0993

The same analysis as for $GEN$ was made for RANF (Sect. ) as well [64]. In the case of RANF, step sizes $k = 2^l$, $l\ge 1$ are of special interest, since such step sizes are implemented on CRAY systems (e.g. see the Cray Math Library Reference Manual SR-2080). Similar as for $GEN$ the lagged subsequences with step sizes 64, 128, 256, 512 show poor spectral test results.

For large power-of-two step sizes we can determine the spectral test for arbitrary multiplicative LCGs with power-of-two moduli $m = 2^\beta$. Let $k = 2^l$, $1\le l < \beta - 2$. Therefore the order of $c:=a^k\!\!\pmod m$ in the multiplicative group ${\bf Z}^*_m$ equals $ord(c) = 2^{\beta - l - 2}$. From () and () we obtain

$$c^n-1\equiv 0\!\!\pmod {2^\alpha} ,\quad 0\le \alpha \le l+2,\quad n \in \{0,\ldots,2^{\beta-2-l} \}.$$ (7)

Thus we get $c-1 \equiv 0\!\!\pmod {2^{\beta-2-l}}$ for all $\lceil \beta/2 \rceil - 2 \le l < \beta-2$. From the lattice structure derived above we conclude that $d_s = 1/\sqrt{2}$ for all $s\ge 2$ and $l$ in the range before. Hence, lagged subsequences from LCGs with power-of-two moduli produce extremely bad lattice structures for ``large'' lags $k = 2^l$ with $\lceil \beta/2 \rceil - 2 \le l < \beta-2$.

Now let $1 \le l < \beta/2 - 1$. Equation () yields $2^{\beta - 2l - 4} (c-1)\equiv 0 \!\!\pmod {2^{\beta-2-l}}$, and therefore $d_2 \ge 1/\sqrt{2^{2\beta-4l-7}}$. Further we observe that $(c-1)^2 \equiv 0 \!\!\pmod {2^{\beta-2-l}}$ for $\lceil \beta/3\rceil - 2 \le l < \beta/2 - 2$ and thus $d_3 \ge 1/\sqrt{6}$ for the latter powers $l$. Similarly, for the same range of $l$, we have $(c-1) (c^2-1) = c^3-c^2-c+1 \equiv 0 \!\!\pmod {2^{\beta-2-l}}$ and therefore $d_s \ge 1/\sqrt{4}$ for $s\ge 4$.

Again consider $GEN$. The table below verifies the calculations above. It exhibits the values $1/d_s^2$ and the normalized spectral tests $S_s$ for $2 \le s \le 8$ and step sizes $k = 2^l$, $l = 13,\ldots, 22$. Note that for $l = 23,\ldots ,45$ we obtain $1/d_s^2 = 2$. The spectral tests for $l = 21$ and $s\ge 5$ can also be verified theoretically in the same way as above (in this case we observe that $c^4-1\equiv 0 \!\!\pmod {2^{\beta-2-l}}$).

$1/d_s^2$
$l\backslash s$	2	3	4	5	6	7	8
22	2	2	2	2	2	2	2
21	$2^5$	6	4	2	2	2	2
20	$2^9$	6	4	4	4	4	4
19	$2^{13}$	6	4	4	4	4	4
18	$2^{17}$	6	4	4	4	4	4
17	$2^{21}$	6	4	4	4	4	4
16	$2^{25}$	6	4	4	4	4	4
15	$2^{29}$	6	4	4	4	4	4
14	2568737986	6	4	4	4	4	4
13	5743563970	384	20	10	10	4	4

$S_s$
$l\backslash s$	2	3	4	5	6	7	8
22	0.00032	0.0049	0.019	0.041	0.068	0.098	0.13
21	0.00091	0.0068	0.022	0.036	0.061	0.088	0.11
20	0.0026	0.0054	0.019	0.044	0.077	0.11	0.15
19	0.0073	0.0043	0.016	0.038	0.068	0.10	0.14
18	0.021	0.0034	0.013	0.033	0.061	0.093	0.13
17	0.058	0.0027	0.011	0.029	0.054	0.084	0.11
16	0.16	0.0021	0.0093	0.025	0.048	0.076	0.11
15	0.47	0.0017	0.0078	0.022	0.043	0.069	0.096
14	0.72	0.0013	0.0066	0.019	0.038	0.062	0.088
13	0.76	0.0085	0.012	0.026	0.054	0.057	0.081

Summary

In Entacher [65] we showed how to analyze correlations within and between lagged subsequences with arbitrary step sizes $k$ generated from LCGs with power-of-two- and prime moduli. The main results of the latter paper are the following:

Consider the full period standard cases of LCGs: (i) $m$ is prime, $a$ is a primitive root modulo $m$, $c = 0$, and $y_0\not=0$, (ii) $m$ is a power of 2, $a\equiv 5\!\!\pmod 8$, and c is odd, and finally (iii) $m$ and $a$ as in (ii) but $c = 0$ and $y_0$ is odd [8,73,130,184,201].

Proposition 3.1   For the analysis of subsequences () of LCGs with power-of-two moduli $m$, the following lattices have to be applied in the spectral test: $L_s (a^k\!\!\pmod m$, $m/\gcd(k,m))$ in Case (ii), and $L_s (a^k\!\!\pmod m$, $m/(4\cdot\gcd(k,m)))$ in Case (iii).

Remark 3.1   The latter proposition shows how to analyze correlations within lagged subsequences. But how to assess correlations between parallel streams obtained by such sequences? Consider $i$ parallel streams ${\bf\omega}_k^{\scriptscriptstyle (j)}$, $0 \le j < i$ in (). In order to study such correlations we have to analyze the set of vectors of the form ${\bf\sigma}_{n} := (x_{kn}$, $x_{kn+1}$, $\ldots$, $x_{kn+i-1})$, $n\ge 0$. Basic calculations, similar as in Subsection above, show that we have to apply $L_i (a, m/\gcd(k,m))$ (Case (ii)) and $L_i (a, m/(4\cdot\gcd(k,m)))$ (Case (iii)) in the spectral test.

In sharp contrast to LCGs with power-of-two moduli, lagged subsequences from prime LCGs (i) exhibit no pure lattice structure in general. As examples, consider $GEN_1 = LCG(2^7-1$,78,0,1) and $GEN_2 = LCG(2^7-1$,114,0,1). The graphics on the left side in the figures below show the lattice structure of all overlapping vectors in dimension $s = 2$ generated from $GEN_1$ (upper graphics) and $GEN_2$, whereas the remaining plots show the structures obtained by the subsequences () with step sizes $k = 2$ and $j = 0,1$. The spectral tests $d_2$ (as described below) are given in the figures as well.

$k = 1$, $j = 0$	$k = 2$, $j = 0$	$k = 2$, $j = 1$
$d_2 = 0.0971$	$d_2 = 0.0830$	$d_2 = 0.0830$

$k = 1$, $j = 0$	$k = 2$, $j = 0$	$k = 2$, $j = 1$
$d_2 = 0.0958$	$d_2 = 0.3162$	$d_2 = 0.3162$

Using the spectral test for the assessment of correlations within lagged subsequences () with step size $k$ generated from prime LCGs, one has to apply the lattice $L_s (a^k\!\!\pmod m, m)$ in the calculation of the test. But in the non-full-period case ($\gcd(k,m-1)>1$), this strategy yields the assessment of the union of all overlapping vectors generated by each subsequence () with $0 \le j < k$. As you may imagine from the figures above, additional correlation analysis should be performed for each single subsequence. Nevertheless, the latter lattice can be applied for finding (bad) subsequences and for a correlation analysis of consecutive blocks (), see Section below.

In order to analyze correlations between lagged subsequences of prime LCGs one has to assess the same set of vectors ${\bf\sigma}_{n}$, $n\ge 0$ as in Remark . Similar as for overlapping vectors of lagged subsequences from prime LCGs, these vectors exhibit no pure lattice structure in general. Therefore the spectral test is not the obvious measure to assess such correlations, exept of an analysis of full-period subsequences.

Spectral Test and Long-Range Correlations

Using the spectral test, the well known ``long-range correlations'' can be exhibited as well. Consider consecutive blocks of proper length $l$

$${\bf\psi}_l^{\scriptscriptstyle (k)}:= (x_{kl+n})_{n=0}^{l-1},\quad k \ge 0,$$ (8)

generated from the linear congruential sequence x. Such consecutive streams of LCGs are easily initialized via the seed $y_0$, and therefore simply provide parallel streams of random numbers for distributed simulations [8,27,28,39,132]. Different concepts of blocking are also supported by various simulation languages [119,122,130] and parallel libraries, e.g. see [23,97,171]. Suppose a LCG is well chosen with respect to the spectral test, then we may assume that each single stream of proper length performs well in practice. But in parallel settings it is also necessary to study correlations between such streams. Therefore we have to analyze vectors of the form

$${\bf\sigma}_{n} := (u_n,u_{n+l},u_{n+2\cdot l},\ldots ,u_{n+(i-1)\cdot l}), \quad n\ge 0,\quad i\ge 1.$$ (9)

Again we consider the multiplicative linear congruential generator $GEN = LCG(2^\beta$, $5^{15}, 0, 1)$. From the basic recurrence $x_{n+j}-x_j \equiv a^j (x_n - x_0)\!\!\pmod m$, $j\ge0$, and from () we get

$${\bf\sigma}_{n} - {\bf\sigma}_{0} \equiv \frac{(x_n - 1)}{4}... ... c^2, \ldots ,c^i )\pmod {{\bf Z}^i}, \quad c:=a^l\!\!\pmod m.$$ (10)

Hence, for $GEN$ the set of all vectors ${\bf\sigma}_{n}$, $n\ge 0$ is contained in the intersection of the shifted lattice ${\bf\sigma}_{0} + L_i(c, m/4)$ with $[0,1[^i$ (compare to the proof of [184, Theorem 7.6 (iii)]). Therefore we can use lattice $L_i(c, m/4)$ to study correlations between a number of $i$ consecutive blocks ($\ref{block}$). The same arguments, yield lattice $L_i(a^l\!\!\pmod m, m)$ for LCGs in Case (i) and (ii).

As an example we use GEN with modulus $m = 2^{48}$, and consider consecutive blocks of length $l = 2^j$, $j\ge 10$. The graphics below shows vectors ${\bf\sigma}_{n}$, $0 \le n \le 1023$, $i = 2, 3$, for block lengths $l = 2^{41}$, $2^{40}$, $2^{39}$ respectively. Below the plots, the spectral tests $d_i$ and the estimates for the number of hyperplanes $n_i$ are given as well. Whereas the correlations between pairs of consecutive streams with decreasing block length $l$ rapidly become better, the spectral tests in dimension $i = 3$ remain stable.

$\bf l = 2^{41}$:

$\bf d_2 = 1/\sqrt{128}$     $\bf n_2 = 16$		$\bf d_3 = 1/\sqrt{6}$     $\bf n_3 = 4$

$\bf l = 2^{40}$:

$\bf d_2 = 1/\sqrt{512}$     $\bf n_2 = 32$		$\bf d_3 = 1/\sqrt{6}$     $\bf n_3 = 4$

$\bf l = 2^{39}$:

$\bf d_2 = 1/\sqrt{2048}$     $\bf n_2 = 64$		$\bf d_3 = 1/\sqrt{6}$     $\bf n_3 = 4$

These graphics exhibit strong ``long-range'' correlations between consecutive streams with large block size. Such long-range correlations between pairs of consecutive blocks have already been studied by DeMatteis and Pagnutti et al. [39,41,38,42,43,44,59]. Using the spectral test to assess such correlations was already suggested by Durst [53] and related concepts can be found in [40,195] ⁸. Similar as DeMatteis et. al. the latter authors applied their correlation analysis only in dimension two for computational and mathematical reasons.

In this section we will update the concepts mentioned above, i.e. we use the spectral test to extend the analysis of correlations between consecutive blocks of random numbers to higher dimensions $i$. The following table shows a normalized spectral test analysis of consecutive blocks obtained from GEN. The table contains results of $S_i$ for block lengths $l = 2^j$, $11 \le j \le 19$ and dimensions $2 \le i \le 8$. From the spectral test results we observe that, no practically relevant consecutive blocks (with power-of-two block lengths) from GEN and related generators should be used in parallel.

Note that in contrast to the spectral tests in Subsection , the tables below exhibit spectral tests of the union of all grids produced from overlapping vectors of subsequences with step size $k = 2^j$.

$i$	$j = 11$	12	13	14	15	16	17	18	19
2	0.5189	0.7827	0.4101	0.4001	0.7036	0.7984	0.6388	0.5922	0.7505
3	0.3252	0.6316	0.9157	0.8660	0.2165	0.0541	0.0135	0.0034	0.0008
4	0.1662	0.0208	0.0026	0.0013	0.0013	0.0013	0.0013	0.0013	0.0013
5	0.0116	0.0116	0.0044	0.0044	0.0044	0.0044	0.0044	0.0044	0.0044
6	0.0202	0.0202	0.0121	0.0121	0.0121	0.0121	0.0121	0.0121	0.0121
7	0.0413	0.0413	0.0191	0.0191	0.0191	0.0191	0.0191	0.0191	0.0191
8	0.0455	0.0455	0.0322	0.0322	0.0322	0.0322	0.0322	0.0322	0.0322

Using only odd block lengths $l$ (hence the block length does not divide the period of the generator which also implies that $LCG(2^\beta$, $a^l\!\!\pmod m, 0,1)$ has full period) provides a simple way against correlations between consecutive blocks obtained from power-of-two LCGs. But previously testing is recommended in this case as well. The table below shows normalized spectral tests $S_s$, $2 \le s \le 8$, using $GEN$ for block lengths $l = 3^j$, $7 \le j \le 15$. Similarly, as for the results below there are no conspicuous correlations for $16 \le j \le 29$.

$i$	$j = 7$	8	9	10	11	12	13	14	15
2	0.5568	0.7586	0.3225	0.5233	0.9388	0.3400	0.4041	0.7146	0.7608
3	0.7885	0.0649	0.7828	0.5840	0.7322	0.5855	0.3608	0.6067	0.8315
4	0.5524	0.6749	0.7581	0.5583	0.5056	0.6959	0.1823	0.5925	0.4150
5	0.6250	0.6372	0.5340	0.5056	0.7240	0.3753	0.1847	0.7383	0.5295
6	0.7074	0.5841	0.7409	0.5772	0.5386	0.5517	0.1676	0.5208	0.6381
7	0.6703	0.5663	0.6403	0.5384	0.6852	0.6355	0.3434	0.6801	0.6012
8	0.7022	0.6511	0.4436	0.6024	0.5562	0.5624	0.4172	0.5401	0.4828

For prime LCGs there are long-range correlations as well. As an example we consider MINSTD. Typical behavior of prime LCGs in long-range correlation analyses with the spectral test is shown in the table below⁹. We derived the normalized spectral test $S_s$, $2 \le s \le 8$ using MINSTD and lattice $L_s(a^l\!\!\pmod {m}, m)$, $a = 16807$, $m = 2^{31}-1$ with block lengths $l = \lfloor \frac{m-1}{i} \rfloor$, for $2 \le i \le 512$. Note that $m-1 = 2\!\cdot\!3^2\!\cdot\!7\!\cdot\!11 \!\cdot\!31\!\cdot\!151\!\cdot\!331$ equals the period of MINSTD. The table reports those results where at least one value $S_s$, $2 \le s \le 8$, turns out to be lower than $0.1$. Column $pf(i)$ gives the prime factors of $i$ since from the results below one may assume that there is a strong impact between the prime factors of the period and those of critical distances $l$ (for more details see the theoretical verification below).

As a first consequence these results require to perform any long-range correlation analysis or calculations of critical distances [38,42,43,59] also in higher dimensions $s$. Consider for example the case $i = 3$, which means that we partition the full period of $G_1$ into three consecutive blocks of length $l = 715827882$, each of which is used as a single stream in parallel. The spectral-test $S_3$ shows that there are strong correlations within all three streams, whereas pairs of these streams are not correlated due to the large value of $S_2$. Further illustration is provided by the measure $n_s$ which in case $i = 3$ equals $n_2 = 48510$ and $n_3 = 2$. Hence, overlapping three dimensional vectors lie in at most two hyper-planes whereas two dimensional vectors lie within a fine lattice structure, due to the large number of hyper-planes estimated in dimension two.

$i$	$pf(i)$	$s = 2$	3	4	5	6	7	8
2	$2$	0.00003
3	$3$	0.8849	0.00120
5	$5$	0.00014	0.00488	0.02762	0.07813
6	$3\!\cdot\!2$	0.8849	0.00120	0.00552	0.01562	0.03051
7	$7$	0.6813	0.5699	0.4995	0.6901	0.7930	0.09129
9	$3^2$	0.5974	0.6704	0.4079	0.5936	0.7703	0.05976	0.08347
10	$2\!\cdot\!5$	0.00689	0.2368	0.6535	0.3313	0.4088	0.26948	0.3764
14	$2\!\cdot\!7$	0.6813	0.5699	0.4995	0.6901	0.7930	0.09129	0.06816
18	$2\!\cdot\!3^2$	0.8906	0.3122	0.644	0.5656	0.8061	0.05976	0.08347
30	$2\!\cdot\!3\!\cdot\!5$	0.9047	0.03419	0.19339	0.5470	0.4277	0.3684	0.5146
31	$31$	0.3290	0.00557	0.03149	0.08908	0.1739	0.2782	0.3886
62	$2\!\cdot\!31$	0.00257	0.08839	0.5000	0.08908	0.1739	0.2782	0.3886
80	$2^4\!\cdot\!5$	0.05772	0.7298	0.8117	0.6029	0.3883	0.6211	0.7482
83	$83$	0.06190	0.7229	0.8283	0.5640	0.6208	0.6901	0.7741
93	$3\!\cdot\!31$	0.5721	0.4139	0.5675	0.05063	0.09886	0.1581	0.2208
124	$2^2\!\cdot\!31$	0.8144	0.08451	0.3894	0.8419	0.4607	0.6409	0.7001
155	$5\!\cdot\!31$	0.01028	0.3536	0.5955	0.5829	0.4934	0.7303	0.5600
251	$251$	0.07531	0.6519	0.5343	0.8393	0.5119	0.5488	0.7099
297	$3^3\!\cdot\!11$	0.09096	0.8742	0.7529	0.6269	0.3823	0.6114	0.5367
358	$2\!\cdot\!179$	0.07184	0.6342	0.6430	0.6453	0.6316	0.5574	0.5763
374	$2\!\cdot\!11\!\cdot\!17$	0.09356	0.4917	0.5778	0.5288	0.6522	0.7707	0.3886

For block lengths $l = (m-1)/i$ with small divisors $i$ of the period $m-1$, we easily can verify the behavior of certain spectral test results in the table above. In this case the order of $c:=a^l\!\!\pmod m$ in the multiplicative group ${\bf Z}^*_m$ equals $ord(c) = i$. Hence for prime numbers $i$ we get $1+c+c^2+\ldots +c^{i-1} \equiv 0\!\!\pmod m$, and therefore the weak spectral test $d_i = 1/\sqrt{i}$. Now consider non-prime divisors $i$. For example let $i=6$. Thus we get $c^6-1 \equiv (c^3-1) (c^3+1) \equiv (c^2-1) (c^4+c^2+1) \equiv 0 \!\!\pmod m$. Let $4 \le s \le 6$. From $c^3+1 \equiv 0\!\!\pmod m$ we obtain $d_s = 1/\sqrt{2}$. For dimension $s=3$ we use $1+c^2+c^4 \equiv 0 \!\!\pmod m$ and $c\equiv -c^4 \!\!\pmod m$, which yield $d_3 = 1/\sqrt{3}$. Similar calculations yield the entries of the following table which are valid for arbitrary primitive roots $a$ modulo $m$, and hence for all full period multiplicative LCGs with prime modulus $m$. The table below exhibits the values $1/d^2_s$ for $2\le s \le 18$.

$i\backslash s$	$2$	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
2	2
3		3
6		3	2	2	2
7						7
9						3	3	3
11										11
14						7	2	2	2	2	2	2	2
18						3	3	2	2	2	2	2	2	2	2	2	2

For $i = 31$ the situation slightly changes. In this case, the (bad) spectral test values depend on the explicit multiplier $a = 16807$. For this multiplier we get $c \equiv 2^{14} \!\!\pmod m$ and therefore $8 c^2 - 1 \equiv 0 \!\!\pmod m$, which yields the bad spectral tests in dimensions $s \ge 3$. Note that $c \equiv 2^\alpha \!\!\pmod m$ for an $\alpha \in \{0,1, \ldots ,30\}$ holds for all primitive roots $a$. Hence, if $i$ equals a multiple of 31 such as $i = 62$ we also obtain bad results.

Parallel Streams from Different LCGs

From arbitrary separate generators, parallel streams of random numbers can be generated as well. This strategy is sometimes recommended in the literature e.g. see [8], or supported by parallel random number libraries [171]. In this section we want to demonstrate the danger of this strategy. As a simple example consider the following three LCGs: Let $a_1 = 264440901825229$, $a_2 = 55151000561141$, and $a_3 = 143150745973517$, and denote the multiplicative LCG with modulus $m = 2^{48}$, seed $x_0 = 1$ and multiplier $a_i$ by $LCG_i$. These multipliers are proposed in [171, Table 7] for use in parallel environments. $LCG_2$ was also proposed by Fishman, see Section . The normalized spectral tests of all three LCGs in the latter dimensions are given in the table below.

$s$	$a_1$	$a_2$	$a_3$
2	0.8603	0.9246	0.8291

$s$	$a_1$	$a_2$	$a_3$
3	0.7906	0.8170	0.7930

Now consider two and three dimensional vectors ${\bf x}_n^{\scriptscriptstyle (2)} := (x_n^{\scriptscriptstyle (1)}, x_n^{\scriptscriptstyle (2)})$ and ${\bf x}_n^{\scriptscriptstyle (3)} :=$ $(x_n^{\scriptscriptstyle (1)}$, $x_n^{\scriptscriptstyle (2)}$, $x_n^{\scriptscriptstyle (3)} )$, such that the $i$'th component of each vector ${\bf x}_n^{\scriptscriptstyle (2)}$ and ${\bf x}_n^{\scriptscriptstyle (3)}$ equals the $n$'th pseudorandom number $x_n^{(i)}$ of $LCG_i$, $i=1,2,3$.

There are no conspicuous correlations between parallel streams generated from these LCGs as we may assume from the scatter plots of $2^{13}$ vectors ${\bf x}_n^{\scriptscriptstyle (2)}$ and ${\bf x}_n^{\scriptscriptstyle (3)}$ given in the following graphics.

But if we change multiplier $a_2 := 158887785558733$ and generate the same plots as before, we easily can exhibit strong correlations between parallel streams from these LCGs, see the graphics below. Note that the new multiplier yields perfect spectral test results $S_2 = 0.8721$ and $S_3 = 0.9057$ as well.