Linear Congruential Generator: LCG

The linear congruential generator (LCG) was proposed by Lehmer in 1949 [152]. We denote this pseudorandom number generator with underlying recursion $x_{n+1}\equiv a x_n + b \!\pmod m$ and seed $x_0$ by $LCG(m,a,b,x_0)$, $a,b,x_0 \in {\bf Z}_m$. Uniform pseudorandom numbers in [0,1[ are obtained by the transformation $u_n := x_n / m$.

Lehmer [152] proposed the generator $LCG(10^8+1, 23, 0, 47594118)$. Quote[83]: By repeating this process he (Lehmer) generates a sequence $u_n$ which he shows has a repetition period of 5.882.352 ( $=(10^8+1)/17 - 1$). An IBM 602A was used to generate 5000 numbers of such a sequence. Four standard tests (unspecified) were applied to check the ``randomness'' and the sequence passed all four. The author observes, however, that all of the members of the sequence he chose were divisible by 17. Further LCGs using multiplier 23 and different moduli ($m = 10^8+1$, $2^{31}-1$, $2^{35}+1$) have been tested empirically in [109].

A. Unreasonable LCGs

Linear congruential generators are very sensitive with respect to changing the parameters. An improper chosen multiplier $a$ may lead to a coarse lattice structure of the vectors ${\bf u}_n^{\scriptscriptstyle (s)}$. Several LCGs have been proposed in such an unlucky way. The parameters mainly have been chosen because of the simplicity of the implementation.

The most famous of these LCGs is the well known ``IBM'' generator RANDU, which is treated in Section . One descendant of RANDU probably may be $LCG(2^{32},477211307,$ $0,1)$ (prime multiplier) which is proposed in [77, p.15]. The spectral test values $S_s$ in dimensions $2 \le s \le 8$ of this generator, given in the table below are even worse than RANDU`s.

$s = 2$	3	4	5	6	7	8
0.6581	0.009451	0.05003	0.1367	0.2608	0.4103	0.5660

The following graphics show zooms into the two and three dimensional unit cubes. Similar as RANDU this LCG produces a fine lattice structure in dimension 2 whereas in dimension 3 strong correlations are exhibited, which are predicted by the spectral test above. The vectors ${\bf u}_n^{\scriptscriptstyle (3)}$ lie on 15 hyperplanes in $[0,1[^3$.

Recently used LCGs with strong deficiencies are for example the generator implemented in the mathematical software DERIVE (see Section ) and the generator $LCG(2^{35}-31,5^5 = 3125, 0, 1)$²given in [204]. Both LCGs show strongly reduced spectral test results in dimension two. For the second LCG the spectral test in dimension $s = 2$ and 3 equal $S_2 = 0.01569$ and $S_3 = 0.8564$. Converse to the case above the zooms into the two dimensional unit cubes below show coarseness of the lattice in dimension two and a fine lattice in dimension three. Note that the latter LCG was already used in the sixties. Quote[155]: The generator was described by Hutchinson [106] and ascribed to Professor D.H. Lehmer. Hutchinson discussed a particular form of the generator for the IBM 7094, in which $p = 2^{35}-31$ is the largest prime less than $2^{35}$ and $A = 5^5$. Unfortunately, his tests on this generator were not published; our own tests and use of the generator confirmed that it is an exceptionally good pseudorandom number generator.

Our worst examples are the generators $G1 = LCG(2^{47}$, $2^{9}+1, 297410973, 0)$, used for the numerical calculations in [100] (first empirical results of the this LCG with different additive constant are given in [109]), and $G2 = LCG(2^{48}$, $2^{24}+3,0,1)$, which corresponds to the NETLIB Module RANDNUM-CRAY (a vectorized random number generator for the Cray X-MP see [199, RAN20] and [14]. Similar as for RANDU the multiplier for these LCGs were chosen to obtain fast implementations (e.g. a multiplication with $2^9 + 1$ is equal to a shift of 9 bits and an addition of 1). The spectral tests both LCGs show spectacularly bad results:

	$s = 2$	3	4	5	6	7	8
$G1$	0.00004024	0.008786	0.1252	0.6168	0.2157	0.1297	0.1022
$G2$	0.6580	0.0002344	0.003127	0.01487	0.04107	0.08414	0.1415

LCGs with power of two moduli $m = 2^\alpha$ and multiplier close to a power of two are well known to produce bad lattice structures, since such multiplier satisfy polynomial equations in $\bf Z_m$ with very small coefficients [181, p. 1026], [126, p. 104], [73,120,179]. One of the first (mixed) LCGs of this type for example is the generator $LCG(2^{35},2^7+1,1,0)$, already proposed by Rotenberg in 1960 [205] (citation from [109,179]). The related $LCG(2^{32},2^7+1,907633385,0)$ for example was implemented in Version 3.0 of Turbo-Pascal (Borland International), for its bad behavior see [60,189]. Such generators, in particular RANDU, have widely been used for a long time and implementations are still available. Some further examples and references concerning the latter LCGs are contained in [36,109,163,180,181] (see also Sect. ).

Another kind of unreasonable generators are LCGs with ``small'' moduli. Examples are $LCG(2^{22}, a, 1731, 0)$, $a \in \{$ 3146757, 2098181, 3146245, 2776669 $\}$, which are available from various libraries at the internet, see [14] [199, RAN8]. These LCGs are well chosen with respect to the spectral test, but they provide period lengths $p = 2^{22}$ which are far to small for actual simulations. Moreover there are well known recommendations on the limit of usable sample sizes for linear congruential generators, e.g. see [162], which make LCGs with such moduli futile for many recent simulations as well. The latter applies also to the generators from [24,116] (the weaknesses of these generators are also pointed out in [210]) and to $LCG(10^8, 31415821, 1, 0)$<sup>3</sup>proposed in [208], and very soon to most of the ``classical'' LCGs from the following section.