The linear congruential generator (LCG) was proposed by Lehmer in
1948 [83].
We denote this pseudorandom number generator
with underlying recursion 
and seed
by 
.
Classical LCGs
ANSIC is the generator employed by the ANSI C rand() function, BSD
version. Note that some versions of the unix online-manual incorrectly
claim this generator's period to be 
.
:
Quote[103]: First suggested by Lewis, Goodman, and Miller in 1969 [84] ( based largely on the fact that this generator is a full period generator) , this generator has in subsequent years passed all new theoretical tests, and (perhaps more importantly) has accumulated a large amount of successful use. Park and Miller[101] do not claim that the generator is ``perfect'' (we will see below that it is not), but only that it is a good minimal standard against which other generators should be judged.
Quote[101]: Our guess is that at some future point we will switch to either a = 48271 or a = 69621. This choice will lead to better spectral test LCGs (see below).
:
Quote[101]: Many multiplicative linear congruential generators are descendents of the infamous RANDU ( System/360 Scientific Subroutine Package, Version III, Programmer's Manual. IBM, White Plains, New York, 1968, p. 77.). This generator was first introduced in the early 1960s; its use soon became widespread ( examples are given ) . In retrospect RANDU was a mistake. The non-prime modulus was selected to facilitate the mod operation and the multiplier was selected primarily because of the simplicity of its binary representation. Research and experience has now made it clear that RANDU represents a flawed generator with no significant redeeming features. It does not have a full period and it has some distinctly non-random characteristics. Knuth calls it ``really horrible'' [67, p. 173,].
:
One of the descendents mentioned above is probably 
(prime multiplier) which is given in [48, p.15,]. The spectral
test values of this generator are worse than RANDU`s
.
Implemented in the SIMSCRIPT II simulation programming language. For references, empirical tests, execution times and lattice tests see [46, 47, 45, 70, 72, 79, 106, 68, 10, 59, 64].
Spectral test for dim. :
Quote [6]: This generator comes from Knuth
[67, p. 102,] and is contained in the totally portable random number
generator HSRPUN from BCSLIB (Boeing Computer Services). The age of this
generator is apparent from its modulus, which dates back to the days of
36-bit computers. The multiplicative version 
is
implemented in the programming language SIMULA and the version with
modulus 
on CDC computers [61]..
Empirical and theoretical tests of this generator are given
in [24, 53, 61].
Spectral tests for dimension :
This generator was used in the BCPL language. References and empirical
results are given in [102]. Excellent spectral test:
This generator corresponds to the URN12 generator in [31, 64].
The latter book contains empirical tests and implementations. Note that
where 
is the multiplier of
BCSLIB. Further empirical results
are given in [79]. Quote [31]:
This generator was for example used in the CUPL language (ref. given)
and was studied by Coveyou and MacPherson [19].
Spectral test for dimension :
Implemented on Apple Computers [62, 108, 64].
Spectral test for dimension
(see also Knuth [67, p. 102,]):
Quote:[67, p. 104,] The generators (with multiplier 
and (BCSLIB) ) are reminders of the good old days - they were
once used extensively since O. Taussky first suggested them in the early 1950s.
Better spectral test results exhibits a LCG with the same multiplier but
modulus 
which is mentioned in several papers (see [88]).
This generator, proposed by Marsaglia [88], is part of a combined
Generator called SUPER-DUPER (combined with a shift-register generator).
Sometimes this LCG itself is called Super-Duper [46, 47].
Quote [88]: As a canditate for the best of
all multipliers, I nominate 69069 
.
This palindromically convoluted multiplier
is easy to remember and has a nearly cubic lattice for moduli
, 
, 
. This generator is sometimes implemented in
the form 
, see [53, p. 89,] and
[120, 64].
These data (
discrepancy estimates ) demonstrate more eloquently than anything
else the inutility of the ``cubic-lattice'' criterion. In fact, one would
be better off choosing multipliers blindly rather than using this criterion;
Spectral tests for dimension and different moduli:
The version yields ``better'' spectral test
results (The spectral test results of this version are given in [6],
instead of the original). The exact discrepancy calculation in
dimension 2 for this generator has been made in [3].
For the versions with modulus
and critical distances are given in [24].
Super-Duper exhibits bad splitting properties, see Section 3.
are published in
[53, 63, 118, 119, 120, 5, 79, 58, 57, 64].
is part of the VAX VMS-Library
(see [53, p. 89,] and [105, 106, 61, 64]) and was
implemented by the Convex Corp. (see [120]).
,
These are the best spectral and lattice test multipliers from a study of Hoaglin [56]. Theoretical and empirical tests are given in [56, 46, 31, 59, 64] and implementations in [31]. For implementations of multiplier 397204094 (SAS and IMSL Lib.) and its theoretical and empirical results see [47, 116]. Fishman[47, p. 40,] writes: Our top five multipliers do not dominate (respectively discrepancy bounds) a = 397204094 and 630360016 (SIMSCRIPT) unambiguously, as in the earlier tables. This lack of discrimination on the part of the lower bounds on discrepancy may be due to the fact that discrepancy is not a rotation invariant measure.
Spectral tests for dim. :
The parameters a in the table below determine the top five LCGs respectively m in an exhaustive analysis of multiplicative congruential random number generators made by Fishman and Moore [47, 44, 45].
Quote [47]: Here a multiplier is said to be optimal if the
distance between adjacent parallel hyperplanes on which k-tuples lie does not
exceed the minimal achievable distance by more than 25 percent for
. This means that the spectral test values are greater than
0.8 (see below and for the first two generators see also [70, 59]).
Empirical result of the second generator can be found in
[72, 79, 53, 121, 82, 42, 61].
Generator 1 and 6 are used in
[58] and [57] to study transformation methods for non-uniform
variates. An implementation is given in [60].
A list of 30 LCGs including RANDU, BCSLIB, APPLE, Super-Duper, DERIVE, and
their spectral tests is given in Knuth[67]. These LCGs have been
selected according to various criteria (``random'' multiplier,
multiplier that guarantee fast implementations, multiplier close to power of
two which produce bad lattice structures [67, 95] ). Some of them
stem from a search for optimal multipliers with respect to
two-dimensional discrepancy made by Borosh and Niederreiter[9].
Empirical and theoretical results of these generators can be found in
[116, 117, 24, 57, 58, 45]. The spectral tests in
dimensions of some Borosh and Niederreiter's LCGs
[9, Table 2,] are given in the table below. Note that
the spectral tests in dimension 2 perform excellent but in
higher dimensions some bad values occur.
1mm
Some Recent LCGs
This is the basic generator for pseudorandom numbers in many different distributions implemented in the NAG Fortran Library [115, Sect. G05,] (also contained in the NAG C Library). Empirical results for this generator are given in [120].
(see also [115]):
DRAND48 is the generator employed by the ANSI C drand48() function, BSD version.
:
This generator was implemented on CRAY systems (see [6, 120, 108, 26, 24, 21, 45, 32]) and used in PASCLIB, a collection of utility subprograms callable from PASCAL on CDC CYBER computers (see [44, 104]). Empirical and theoretical tests of this generator are given in the papers above.
Spectral test for dim. :
This is the PRNG implemented in the mathematical software Maple.
Email(From ddubois@maplesoft.com Mar 13 1996):
is a previously determined prime with 427419669081
a proven primitive element in 
. NOTE: the results of the spectral
test for this generator are very good.
There was an article written by Zaven A. Karian and Rohit Goyal that appeared in Volume 1, Number 1, Spring 1994 of the Maple Technical Newsletter entitled ``Random Number Generation and Testing''. It offers a detailed analysis of Maple's rand() command (For orders and information please contact: Birkhauser Verlag AG, Klosterberg 23, P.O. Box 133 CH-4010, Basel, Switzerland, Phone: 41 61 271 7400).
Spectral test for dimensions (see also [108]):
Email(From swh@aloha.com Mar 14 1996):
The DERIVE random number generator maintains a random integer in the
interval 
to calculate user requested random integers in a given
range. Given a random integer n, the next random integer is generated by the
formula MOD (3141592653*n + 1, ). Information:
Soft Warehouse, Inc. (the authors of DERIVE, A Mathematical Assistant),
3660 Waialae Avenue, Suite 304
Honolulu, HI 96816-3236 U.S.A. Web page: http://www.derive.com
The multiplier probably stems from Knuth [67, p. 32,44,102,],
who studied 
Quote:[67, p. 103,] The latter LCG shows a ``random''
multiplier; this generator has satisfactorily passed numerous empirical tests
for randomness, but it does not have especially good spectral test values
for dimensions 
. Empirical results
of this generator are given in [116].
Spectral test for dimensions (observe the poor
lattice of DERIVE in dim. 2):
LCG(m, a, 0, 1)
These generators have been implemented in several versions of C-RAND [108, 109, 110, 55], a package for generating nonuniform random variates. They were proposed by Ahrens et al. [4, 30, 108]. Empirical results of the first generator are given in [53, 57, 64] .
Pierre L'Ecuyer used spectral tests and Beyer ratios to search for
good multipliers a for LCG(m,a,0,1) with selected prime moduli m.
In order to propose combined LCGs [70] he obtained the multipliers
(for faster implementations) given in Section 5.2.
The latter paper contains portable implementations and results of a battery of
empirical tests for Generator 4.2.3. This LCG is also used as an
example to show that LCGs are not recommended to generate random variates
by the ratio of uniforms method [58]. For a similar purpose
Generator 4.2.1 is applied in [59] as an example to show that
LCGs with small multiplier are useless to generate pseudorandom numbers
for other distributions via the rejection method. Discrepancy bounds,
spectral tests and Beyer quotients for the generators 4.2.1 to 4.2.6 are
given in [45].
In [78] L'Ecuyer et. al. suggested the following
``good-lattice'' LCGs (see also [71]).
Recent tables of LCGs with different moduli 
and good lattice structures up to dimension s = 32 are given in
[76]. The tables below present those LCGs with very large moduli.
The LCGs below are selected according to the measure
M8 which denotes the minimum of the spectral tests
.
This LCG closely approximates the
subtract with borrow (SWB) [91] pseudorandom number generator
which is implemented in
Mathematica
(SWB version 7 with period 
given in Table 2 of the
latter paper). SWB and the similar add with carry (AWC) generators
are almost equivalent to LCGs with large moduli.
This was shown by Tezuka, L`Ecuyer and Couture
[113, 114, 15, 16, 75].
Quote[75] : More precisely, the absolute difference
between the 
produced by the appoximating LCG and that produced
by the SWB generator is bounded by 1/a.
It turned out that these generators have extremely bad lattice
structures in high dimensions. In case of the Mathematica generator
the (non-normalized) spectral test 
for dimensions
(
for 
).
Moreover, certain three dimensional vectors of
non-successive values of such generators lie in parallel planes that are
at least 
apart [75].
Another similar SWB generator given in [91, Vers. 3 Tab. 2,]
and used as a component of the combined generator proposed in
[90] is almost equivalent to
.
Beyer and spectral tests up to dimensions 50 of this generator are given
in [114, 15], empirical results in [72].
The lattice structure of the combined generator [90] is
examined in [15]. Further empirical results which exhibit
defects of AWC and SWB generators are given in [43].
Similar as for MATH above, this LCG approximates the
SWB generator proposed in [91, Vers. 10 Tab. 2,]. A Fortran
implementation and timings of RCARRY are given in [61].
Quote[75] : The vectors 
produced by that generator lie within a distance of
to a pair of planes which are apart.