next up previous contents
Next: C. More Relevant LCGs Up: A collection of classical Previous: Linear Congruential Generator: LCG   Contents

Subsections


B    Classical LCGs



ANSIC

$LCG(2^{31}, 1103515245, 12345, 12345)$
\includegraphics[width=5cm]{eps/ansic.eps}

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 $2^{32}$.

Theory:
Park and Miller [189] writes: its deficiencies are well known- according to Berkeley 4.2 documentation, the low bits of the numbers generated are not very random. Spectral test for dim. $2 \le s \le 8$:
0.84 0.52 0.63 0.49 0.68 0.43 0.54

Empirics:
See [61,70,26,28,29,87,150,140,137,146,145,151,234]
Implementations:
Source code in [200, p. 276 (not recommended!)].
Literature:
[171]; Times for various generators in C (incl. ANSIC) are given in Ripley [203, p. 160]. Quote[203]: The Unix generator rand has been replaced by drand48 (see Section [*]) which is far too slow and by a feedback generator random of the type $F(r,s,+)$.



MINSTD

$LCG(2^{31}\!\!-\!\!1, a = 7^5 = 16807, 0, 1)$
\includegraphics[width=5cm]{eps/minstd.eps}

Quote[200]: First suggested by Lewis, Goodman, and Miller in 1969 [155] ( 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[189] 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[189]: 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).

Theory:
``Lattice'' tests, execution time results, packing measures, discrepancy bounds and others can be found in [10,51,73,74,75,104,139]. An analysis of the lattice structure is given in [131,163], and critical distances in [38]. Spectral test for dimensions $2 \le s \le 8$:

16807 0.3375 0.4412 0.5752 0.7361 0.6454 0.5711 0.6096
48271 0.8960 0.8269 0.8506 0.7332 0.8078 0.5865 0.4364
69621 0.7836 0.9205 0.8516 0.7318 0.7667 0.6628 0.7845

Empirics:
See [1,7,13,26,28,31,45,51,70,68,71,73,74,76,85,87,88,111,118,121,128,150,133,140,137,146,145,151,155,178,221,232,230,231,233,234]
Implementations:
For implementations in commercial software and source code see [17,45,51,73,74,130,139,96,171,179,189,199,203] , MATLAB 4.0 [172,177]4, the CNCL [206] and IMSL (see [14, RNUN]) Libraries, and the simulation software ACSL, AweSim, SIMAN/Arena and Slam II [130,119]. Source code of MINSTD and MINSTD with a shuffling algorithm added are given in [200]. For fast implementations using multiplier 48271 and 69621 see [22,200], [165, Microsoft Fortran system generator]. Tests for these multipliers are given in [73,165].
Literature:
[9,24,26,73,79,91,102,98,107,118,120,122,134,171,179,193,201,202,204,209,222]



RANDU

$LCG(2^{31}, 2^{16}+3 = 65539, 0, 1)$
\includegraphics[width=5cm]{eps/randu_lattice.eps}

Quote[189]: Many multiplicative linear congruential generators are descendants 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'' [126, p. 173].

Theory:
Lattice ratings in: [37,51,73,74,126,139,163]. Critical distances in [42]. Spectral test for dim. $2 \le s \le 8$:
0.93 0.012 0.059 0.16 0.29 0.45 0.62

Empirics:
[7,12,51,52,73,74,85,87,118,150,140,137,146,145,151,156,194,234]
Implementations:
Three implementations: KERAND (IRCC assambler version of RANDU), original RANDU (IBM Corporation (1970) in FORTRAN) and RANDU as used in SPSS are given in [51, pp. 73]. Further implementations can be found in [189, Sect. 4]. For combined generators using RANDU see [51, pp. 28].
Literature:
[17,18,37,48,67,91,92,107,118,120,130,176,179,202,222];
A history of the beginning of RANDU is given in [51, p. 2].



SIMSCRIPT

$LCG(2^{31}\!-\!1, 630360016, 0, 1)$
\includegraphics[width=5.0cm]{eps/simscript.eps}

Implemented in the SIMSCRIPT II and INSIGHT simulation programming language and employed by the FORTRAN RAN function [37]. For references, implementations, empirical tests, execution times and lattice tests see [12,17,24,37,74,75,73,91,104,118,128,130,131,133,139,140,146,145,137,130,160,169,171,193,192,202,203]. Source codes in FORTRAN, Pascal and C, which support seed management in order to provide disjoint streams of random numbers, are given in [130, Sect. 7.6].

Note that $630360016 = 14^{29} \pmod{2^{31}-1}$. Quote [192]: Lehmer [153,226] suggested $K = 14^{29}, m = 2^{31}-1$ (a prime Mersenne number). Fourteen was chosen because it is a primitive root modulo $m$; a multiplicative group of order $2^{31}-2$ (cycle length) was generated. Raising 14 to the $v$-th power where $v$ is relatively prime to the cycle length gives another primitive root modulo $m$. Choosing $v = 29$ introduces ``randomness'' into the number sequence.

Spectral test for dim. $2 \le s \le 8$:
0.82 0.43 0.78 0.80 0.57 0.68 0.72



BCSLIB

$LCG(2^{35}, 5^{15}, 7261067085, 0)$
\includegraphics[width=5.0cm]{eps/bcslib.eps}

Quote [8]: This generator comes from Knuth [126, 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 (e.g. implemented on UNIVAC machines [130, p. 428]).

The multiplicative versions $LCG(2^{35},5^{15},0,1)$ is implemented in the programming language SIMULA, and the version with modulus $2^{47}$ on CDC computers [107] [25, V104]. In [16] a version with modulus $2^{48}$ is tested in different parallel settings (see also Sect. [*]). Empirical and theoretical tests of these generators are given in [8,36,46,42,85,107].

Spectral test for dimensions $2 \le s \le 8$:

LCG $s = 2$ 3 4 5 6 7 8
$LCG(2^{35}, 5^{15}, 7261067085, 0)$ 0.7460 0.8784 0.7995 0.4851 0.6919 0.5233 0.6934
$LCG(2^{35},5^{15},0,1)$ 0.5809 0.4145 0.8004 0.6401 0.6951 0.6379 0.7473
$LCG(2^{47},5^{15},0,1)$ 0.6794 0.6248 0.6158 0.5512 0.4588 0.6416 0.7309
$LCG(2^{48},5^{15},0,1)$ 0.9599 0.5761 0.5178 0.4799 0.6001 0.6956 0.6715



URN12

$LCG(2^{31}, 452807053, 0, 1)$
\includegraphics[width=5.0cm]{eps/urn12.eps}

This generator corresponds to the URN12 (URN11) generator in [51,118]. The latter books contain empirical tests and implementations. Note that $5^{15}\!\!\pmod{2^{31}} = 452807053$ where $5^{15}$ is the multiplier of BCSLIB. Further empirical results are given in [12,52,140,137,146,145].

Quote [51]: This generator was for example used in the CUPL language (ref. given) and was studied by Coveyou and MacPherson [36].

Spectral test for dim. $2 \le s \le 8$:
0.766 0.772 0.490 0.398 0.705 0.635 0.436



APPLE

$LCG(2^{35}, 5^{13} = 1220703125, 0, 1)$
\includegraphics[width=5.0cm]{eps/apple.eps}

Implemented on Apple Computers [118,110,216]. Spectral test for dimensions $2 \le s \le 8$ and different moduli $m$:

$m$ $s = 2$ 3 4 5 6 7 8
$2^{32}$ 0.7930 0.7431 0.6291 0.6531 0.5689 0.7445 0.5946
$2^{35}-31$ 0.7764 0.5195 0.5498 0.6873 0.6321 0.4211 0.5981
$\bf 2^{35}$ 0.4746 0.3715 0.6376 0.6124 0.7416 0.6781 0.7473
$2^{39}$ 0.9142 0.2953 0.4650 0.5498 0.6443 0.6482 0.6395
$2^{46}$ 0.5714 0.6665 0.5530 0.6178 0.5913 0.5964 0.5821

Quote:[126, p. 104] The generators (with multiplier $5^{13}$ and $5^{15}$ (BCSLIB) ) are reminders of the good old days - they were once used extensively since O. Taussky first suggested them in the early 1950s (see also [109,153,212]).

Better spectral test results exhibits a LCG with the same multiplier but with modulus $m = 2^{35}-31$ [163], $m = 2^{46}$ [171] or $m = 2^{32}$. The latter version is implemented in the simulation language SIMULA for BS 2000. Empirical results for different moduli are given in [12,109]. Jansson [109] used modulus $m = 2^{39}$.



Super-Duper

$LCG(2^{32}, 69069, 0, 1)$
\includegraphics[width=5.0cm]{eps/superduper.eps}

This generator, proposed by George Marsaglia [163,168,165], is part of a combined Generator called SUPER-DUPER5 (combined with a shift-register generator).

Quote [163]: As a candidate for the best of all multipliers, I nominate 69069 $=3\cdot 7\cdot 11\cdot 13\cdot 23$ . This palindromically convoluted multiplier is easy to remember and has a nearly cubic lattice for moduli $2^{32}$, $2^{35}$, $2^{36}$. Super-Duper was sometimes implemented in the form $LCG(2^{32}, 69069, 1, 0)$, see [85, p. 89] and [118,233].

Theory:
Lattice considerations can be found in [37,75,163] and spectral tests in [8,10,51,126,73,139]. Niederreiter [181, p. 1027] derived an upper bound for the discrepancy in dimension 2 for this generator and found multipliers (see also [75, p. 35], [3, p. 81] and [15]) with smaller discrepancy: Quote [181]: Specific multipliers have also been proposed on the basis of the ``cubic-lattice criterion'' $\ldots$ 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 test for dimensions $2 \le s \le 8$ and different moduli:

$2^{32}$ 0.4625 0.3131 0.4572 0.5529 0.3767 0.4967 0.6852
$2^{35}$ 0.6935 0.8595 0.6347 0.7000 0.2664 0.3690 0.5284
$2^{36}$ 0.4904 0.6822 0.7760 0.6094 0.4746 0.3342 0.4845

The version $LCG(2^{32}, 69069, 1, 0)$ yields ``better'' spectral test results (The spectral test results of this version are given in [8], instead of the original). The exact discrepancy calculation for overlapping tuples in dimension 2 has been carried out in [5]. For the versions with modulus $2^{35}$ and $2^{36}$ critical distances are given in [42]. Super-Duper exhibits rather bad splitting properties, see Section [*].

Empirics:
Empirical results of both versions are published in [2,7,12,85,90,101,102,103,111,118,124,140,137,146,145,160,230,231,233].
Implementations:
Quote[164]: The (combined) generator Super-Duper is part of the McGill Random Number Package widely used at several hundred locations. The LCG was implemented on IBM computers [75]. The version $LCG(2^{32}, 69069, 1, 0)$ is part of the VAX VMS-Library (see [85, p. 89] and [107,118,168,202,203]) and was implemented by the Convex Corp. (see [233]).



HoaglinLCGs


\includegraphics[width=5.0cm]{eps/hoaglin3.eps}

$a \in \{ 1078318381, 1203248318, {\bf 397204094}, 2027812808, 1323257245, 764261123 \} $

These are the best spectral and lattice test multipliers from a study of Hoaglin [99]. Theoretical and empirical tests are given in [12,51,74,99,104,118,193] and implementations in [51]. For implementations of multiplier 397204094 (SAS and IMSL Library) and its theoretical and empirical results see [75,79,130,179,227]. Fishman[75, 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. $2 \le s \le 8$:

$a\backslash s$ 2 3 4 5 6 7 8
1078318381 0.9442 0.6790 0.6684 0.7137 0.7252 0.6482 0.6265
1203248318 0.9086 0.8673 0.8092 0.6997 0.6389 0.6324 0.6695
397204094 0.5564 0.5748 0.6674 0.7678 0.5947 0.5815 0.7181
2027812808 0.6883 0.6012 0.7059 0.6976 0.6356 0.7432 0.6917
1323257245 0.7298 0.6106 0.6715 0.7393 0.6389 0.6726 0.6430
764261123 0.7309 0.7081 0.7153 0.7710 0.6887 0.6143 0.6484



FishmanLCGs


\includegraphics[width=5.0cm]{eps/fish2.eps}

The parameters $a$ in the table below determine the top five generators respectively $m$ in an exhaustive analysis of multiplicative congruential random number generators made by Fishman and Moore [72,73,75].

Quote [75]: 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 $k = 2,\ldots,6$. This means that the spectral test values are greater than 0.8 (see the table below and for the first two generators see also [104,131]). Further references and empirical results for Fishman-LCGs (mainly for generator 1 and 2) can be found in [67,69,68,70,85,87,91,92,89,103,107,112,117,150,133,140,137,146,145,151,156,171,193,234]. Generator 1 and 6 are used in [102] and [101] to study transformation methods for non-uniform variates. An implementation is given in [105]. Generator 1 is implemented in the simulation language GPSS/H [130,139,157,169,207].

no. $m$ $a\backslash s$ 2 3 4 5 6 7 8
1   742938285 0.8672 0.8607 0.8627 0.8319 0.834 0.6239 0.7067
2   950706376 0.857 0.8985 0.8691 0.8337 0.8274 0.5916 0.5981
3 $2^{31}-1$ 1226874159 0.8411 0.8787 0.8255 0.8378 0.8444 0.6277 0.5981
4   62089911 0.8930 0.8903 0.8575 0.8630 0.8249 0.7622 0.6020
5   1343714438 0.8236 0.8324 0.8245 0.8262 0.8254 0.7440 0.4915
no. $m$ $a\backslash s$ 2 3 4 5 6 7 8
6   1099087573 0.8920 0.8563 0.8603 0.8420 0.8325 0.5547 0.7506
7   2396548189 0.8571 0.9238 0.8316 0.8248 0.8247 0.6664 0.709
8 $2^{32}$ 2824527309 0.9220 0.8235 0.850 0.8451 0.8332 0.6983 0.5512
9   3934873077 0.8675 0.8287 0.8278 0.8361 0.8212 0.7188 0.7616
10   392314069 0.9095 0.8292 0.8536 0.8489 0.8198 0.6047 0.6084
no. $m$ $a\backslash s$ 2 3 4 5 6 7 8
11   68909602460261 0.8253 0.8579 0.8222 0.8492 0.8230 0.6971 0.5275
12   33952834046453 0.9282 0.8476 0.8575 0.8353 0.8215 0.5289 0.6383
13 $2^{48}$ 43272750451645 0.8368 0.8262 0.8230 0.8400 0.8213 0.5993 0.6171
14   127107890972165 0.8531 0.8193 0.8216 0.8495 0.8224 0.4504 0.5934
15   55151000561141 0.9246 0.8170 0.9240 0.8278 0.8394 0.6274 0.4471



Knuth - and Borosh and Niederreiter LCGs

A list of 30 LCGs including RANDU, BCSLIB, APPLE, Super-Duper, DERIVE, and their spectral tests is given in Knuth [126]. 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 [73,126,181] ). Some of them stem from a search for optimal multipliers with respect to two-dimensional discrepancy made by Borosh and Niederreiter Niederreiter [15]. Empirical and theoretical results of these generators can be found in [69,42,73,101,102,196,227,228]. The spectral tests in dimensions $2 \le s \le 8$ of some Borosh and Niederreiter's LCGs [15, Table 2] are given in the table below. Note that the spectral tests in dimension 2 perform excellent but as one may guess in higher dimensions some bad values occur. An extension of Borosh and Niederreiter`s search to prime moduli is given in [21]. Note that the generators, obtained by the latter study, behave satisfactory in the spectral test in higher dimensions as well.

$LCG(2^n,a,0,1)$
$n$ $a$ $s = 2$ 3 4 5 6 7 8
15 13821 0.520 0.480 0.530 0.781 0.690 0.580 0.648
16 47485 0.558 0.381 0.765 0.369 0.486 0.587 0.665
17 82669 0.915 0.474 0.824 0.406 0.548 0.673 0.721
18 160461 0.928 0.595 0.701 0.612 0.518 0.646 0.750
19 217293 0.940 0.473 0.788 0.697 0.596 0.676 0.725
20 387645 0.847 0.484 0.749 0.787 0.581 0.750 0.595
21 886269 0.626 0.24 0.337 0.628 0.634 0.679 0.668
22 3067221 0.698 0.095 0.283 0.547 0.729 0.632 0.530
23 3513381 0.896 0.54 0.748 0.437 0.531 0.719 0.707
24 12268885 0.736 0.060 0.200 0.414 0.657 0.652 0.515
25 21149085 0.923 0.745 0.505 0.452 0.721 0.610 0.562
26 41430805 0.682 0.526 0.665 0.568 0.585 0.737 0.484
27 96801245 0.702 0.719 0.518 0.601 0.598 0.690 0.678
28 169764749 0.541 0.566 0.648 0.775 0.535 0.620 0.648
29 338335805 0.721 0.736 0.799 0.502 0.678 0.680 0.675
30 777138309 0.654 0.632 0.646 0.644 0.625 0.613 0.723
31 906185749 0.569 0.729 0.594 0.753 0.661 0.601 0.729
32 3039177861 0.433 0.555 0.417 0.713 0.748 0.454 0.626
33 6223592213 0.565 0.571 0.668 0.554 0.511 0.710 0.606
34 10618587253 0.694 0.558 0.688 0.713 0.443 0.552 0.667
35 21733031525 0.796 0.798 0.682 0.589 0.660 0.517 0.550

$LCG(2^n,a,1,0)$
$s = 2$ 3 4 5 6 7 8
0.839 0.302 0.673 0.703 0.698 0.476 0.545
0.790 0.511 0.541 0.839 0.546 0.610 0.661
0.915 0.700 0.609 0.308 0.435 0.552 0.648
0.921 0.375 0.792 0.464 0.671 0.771 0.665
0.921 0.298 0.777 0.665 0.742 0.716 0.610
0.837 0.716 0.529 0.685 0.670 0.665 0.530
0.899 0.605 0.476 0.653 0.685 0.557 0.688
0.900 0.060 0.200 0.414 0.579 0.798 0.713
0.896 0.680 0.551 0.332 0.421 0.590 0.695
0.847 0.038 0.142 0.314 0.522 0.743 0.707
0.804 0.634 0.780 0.538 0.637 0.599 0.607
0.861 0.810 0.533 0.818 0.679 0.640 0.604
0.825 0.890 0.713 0.694 0.577 0.767 0.586
0.804 0.680 0.709 0.736 0.509 0.561 0.656
0.705 0.849 0.597 0.457 0.805 0.607 0.688
0.728 0.625 0.457 0.488 0.553 0.684 0.608
0.946 0.612 0.420 0.631 0.525 0.493 0.643
0.865 0.447 0.590 0.690 0.697 0.734 0.637
0.920 0.719 0.595 0.460 0.405 0.583 0.582
0.754 0.389 0.912 0.760 0.594 0.540 0.592
0.771 0.502 0.770 0.580 0.524 0.614 0.600

 



AndersonLCGs

$LCG(2^{48}, a, 0, 1)$

Using the spectral test, Anderson [8] made a search for good multipliers for multiplicative LCGs with modulus $2^{48}$. Different to Fishman [72] who did an exhaustive search, Anderson used a LCG (see Sect. [*]) to perform a partial search over multiplier $a = 8k + 5$. In the table below we give the list of 20 ``acceptable'' ($S_s \ge 0.75$, $2\le s \le 6$) multiplier with their spectral tests. The search of Anderson was extended by Masuda and Zimmerman [171]. They got 1615 multiplier for modulus $m = 2^{48}$ and 527 for $m = 2^{46}$. Both searches were motivated in order to obtain LCGs for use in parallel environments.

$a$ $s = 2$ 3 4 5 6 7 8
18776556235061 0.85 0.79 0.79 0.82 0.85 0.58 0.65
53579223172421 0.86 0.81 0.79 0.81 0.80 0.51 0.67
31434765394133 0.84 0.81 0.78 0.84 0.78 0.65 0.63
22686095011669 0.77 0.93 0.81 0.79 0.81 0.59 0.62
2197506174885 0.80 0.86 0.80 0.77 0.79 0.65 0.66
690632340005 0.78 0.79 0.79 0.79 0.77 0.67 0.67
58408894744493 0.77 0.82 0.84 0.80 0.77 0.60 0.40
30232061565421 0.88 0.87 0.78 0.77 0.76 0.55 0.52
21543881559045 0.82 0.85 0.82 0.76 0.82 0.66 0.65
61900184494637 0.76 0.92 0.81 0.79 0.77 0.57 0.65

$a$ $s = 2$ 3 4 5 6 7 8
39039429233749 0.92 0.91 0.81 0.78 0.76 0.59 0.57
42127110958077 0.78 0.83 0.81 0.78 0.76 0.40 0.56
16033605563477 0.79 0.89 0.77 0.76 0.77 0.54 0.48
11122949907021 0.76 0.76 0.77 0.81 0.79 0.72 0.48
39447896541885 0.92 0.83 0.88 0.75 0.78 0.70 0.50
5767270508013 0.92 0.77 0.83 0.75 0.76 0.44 0.57
8777141160869 0.92 0.77 0.75 0.76 0.81 0.47 0.57
36278420839141 0.78 0.75 0.84 0.82 0.79 0.64 0.69
47263418859061 0.89 0.82 0.76 0.79 0.75 0.66 0.61
6232495950549 0.79 0.75 0.84 0.81 0.77 0.66 0.71

 



DERIVE

$LCG(2^{32}, 3141592653, 1, 0)$
\includegraphics[width=5.0cm]{eps/derive.eps}

Email(From swh@aloha.com Mar 14 1996): The DERIVE random number generator maintains a random integer in the interval $[0, 2^{32}-1]$ 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, $2^{32}$). Information: Soft Warehouse, Inc. (the authors of DERIVE, A Mathematical Assistant), 3660 Waialae Avenue, Suite 304 Honolulu, HI 96816-3236 U.S.A. http://www.derive.com

The multiplier probably stems from Knuth [126, p. 32,44,102], who studied $LCG(2^{35}$, $3141592653,2718281829,0)$ (note that the digits of the multiplier equal the first digits of $\pi$ in its decimal representation).

Quote:[126, 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 $2\le s \le 4$.

Empirical results from DERIVE are given in [227]. Ripley [203] quotes a similar multiplier $a = 3141592621$ which was used on Atari ST machines. Further ``related'' generators are $LCG(10^8, 31415821, 1, 0)$ from [208] (see also Sect. A) and $LCG(2^{31}$, 314159269, 453806245, 0) which was proposed in [127, p. 240] (quote from [130]). The latter multiplier is also mentioned in [165, make.txt]. Anderson [8] used $LCG(2^{43}$, 3141592653, 2718281, 1) to perform a random search for good multiplier with respect to the spectral test for multiplicative LCGs with modulus $2^{48}$ (see also [171]). The table below presents spectral tests for DERIVE with different moduli $m$ (observe the poor result for $m = 2^{32}$ in dimension $s = 2$):

$2^{32}$ 0.0972 0.5551 0.5479 0.3216 0.6426 0.5210 0.6731
$2^{35}$ 0.2749 0.2776 0.3258 0.2122 0.4544 0.6721 0.6984
$2^{43}$ 0.4073 0.4604 0.3966 0.3599 0.4786 0.7039 0.6357



Further Classical LCGs

This section contains further LCGs implemented in different software or some of which are mentioned in the literature.

  1. $LCG(2^{32}, 2147001325, 715136305, 0)$ was used in the BCPL language. References and empirical results are given in [194]. Excellent spectral test for $2 \le s \le 8$: 0.91, 0.85, 0.88, 0.78, 0.55, 0.60, 0.65.

  2. $LCG(2^{32}, 22695477, 1, 0)$ contained in a Turbo C++ Library (function rand()) [213]. The latter book also points out some defects in former implementations. Spectral test for dim. $2 \le s \le 8$: 0.86, 0.60, 0.67, 0.68, 0.73, 0.67, 0.46.

  3. $LCG(2^{32}, 134775813, 1, 0)$ implemented in TurboPascal, Version 7.0 [176]; Spectral test for dim. $2 \le s \le 8$: 0.75, 0.40, 0.60, 0.60, 0.76, 0.35, 0.40.

  4. $LCG(2^{48}, 5^{17}, 1, 0)$ mentioned in [160]. Similar as BCSLIB and APPLE the latter LCG (with different moduli) was already used in the 1950s [153,109,212]. Spectral test for dim. $2 \le s \le 8$: 0.68, 0.64, 0.70, 0.59, 0.57, 0.65, 0.74.

  5. $LCG(2^{35}, 8404997, 1, 0)$ implemented in the simulation software GLIM (generalized linear interactive modeling) [86]. Spectral test for dim. $2 \le s \le 8$: 0.56, 0.66, 0.29, 0.73, 0.61, 0.67, 0.50.

  6. $LCG(2^{47}, 84000335758957,0,1)$ was implemented on CDC computers [122,124,125]. Spectral test for dim. $2 \le s \le 8$: 0.65, 0.42, 0.49, 0.68, 0.58, 0.57, 0.74.


next up previous contents
Next: C. More Relevant LCGs Up: A collection of classical Previous: Linear Congruential Generator: LCG   Contents
Karl Entacher 2000-06-16