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 and seed by , . Uniform pseudorandom numbers in [0,1[ are obtained by the transformation .

Lehmer [152] proposed the generator
.
**Quote**[83]: *By repeating this process he *(Lehmer)*
generates a sequence which he shows has a repetition period
of 5.882.352 *(
)*.
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 (,
, ) have been tested empirically in [109].

Linear congruential generators are very sensitive with respect to changing the parameters. An improper chosen multiplier may lead to a coarse lattice structure of the vectors . 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 (prime multiplier) which is proposed in [77, p.15]. The spectral test values in dimensions of this generator, given in the table below are even worse than RANDU`s.

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 lie on 15 hyperplanes in .

Recently used LCGs with strong deficiencies are for example the generator
implemented in the mathematical software DERIVE (see Section ) and
the generator
^{2}given in [204].
Both LCGs show strongly reduced spectral test results in dimension two.
For the second LCG the spectral test in dimension and 3 equal
and .
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 is the largest prime less than and
. 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 , , used for the numerical calculations in [100] (first empirical results of the this LCG with different additive constant are given in [109]), and , , 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 is equal to a shift of 9 bits and an addition of 1). The spectral tests both LCGs show spectacularly bad results:

3 | 4 | 5 | 6 | 7 | 8 | ||

0.00004024 |
0.008786 |
0.1252 | 0.6168 | 0.2157 | 0.1297 | 0.1022 | |

0.6580 | 0.0002344 |
0.003127 |
0.01487 |
0.04107 |
0.08414 |
0.1415 |

LCGs with power of two moduli and multiplier close to a power of two are well known to produce bad lattice structures, since such multiplier satisfy polynomial equations in 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 , already proposed by Rotenberg in 1960 [205] (citation from [109,179]). The related 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
, 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 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
^{3}proposed in [208], and very soon to
most of the ``classical'' LCGs from the following section.