next up previous contents
Next: Parallel LCGs Up: A collection of classical Previous: B    Classical LCGs   Contents

Subsections


C. More Relevant LCGs



NAG

$LCG(2^{59}, 13^{13}, 0, 123456789 (2^{32}+1))$
\includegraphics[width=5.0cm]{eps/nag.eps}

This is the basic generator for pseudorandom numbers in many different distributions implemented in the NAG Fortran Library [225, Sect. G05], [122,179] (also contained in the NAG C Library). Empirical results for this generator are given in [123,198,232,233]. For implementations in parallel environments see [95,97]. Usable limit considerations are contained in [162]. For lattice analyses and spectral tests and Beyer quotients up to dimensions 20 see [4,37,201]. Spectral test for dim. $2 \le s \le 8$ (see also [225]):

0.8423 0.7288 0.7426 0.5771 0.6351 0.5217 0.5455



DRAND48

$LCG(2^{48}, 25214903917, 11, 0)$
\includegraphics[width=5.0cm]{eps/drand48.eps}

DRAND48 is the generator employed by the ANSI C drand48() function, BSD version.

Spectral test for dimensions $2 \le s \le 8$:
0.51 0.80 0.45 0.58 0.66 0.80 0.60
Execution times are given in [203] and empirical results in [26,28,78].



RANF

$LCG(2^{48}, 44485709377909, 0, 1)$
\includegraphics[width=5.0cm]{eps/cray.eps}

This generator was implemented on CRAY systems (for references and theoretical and empirical results see [8,11,26,27,28,39,40,42,44,53,73,79,92,171,199,197,216,230,233] and the CRAY homepage) and used in PASCLIB on CDC6 CYBER computers (see [37,72,201] [25, G900]). The multiplier also corresponds to the default multiplier in the 48 bit LCG (with prime added) implementation in the SPRNG library [23] and was also mentioned in [195].

Spectral test for dim. $2 \le s \le 8$:
0.827 0.742 0.398 0.731 0.618 0.667 0.564



MAPLE

$LCG(10^{12}\!\!-\!\!11, 427419669081, 0, 1)$
\includegraphics[width=5.0cm]{eps/maple.eps}


This is the PRNG implemented in the mathematical software Maple.

Email(From ddubois@maplesoft.com Mar 13 1996): $10^{12}-11$ is a previously determined prime with 427419669081 a proven primitive element in ${\bf Z}_p$. 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 dim. $2 \le s \le 8$ (see also [216]):
0.75 0.74 0.65 0.73 0.63 0.56 0.56



Ahrens-DieterLCGs

$LCG(m, a, 0, 1)$
\includegraphics[width=5.0cm]{eps/crand1.eps}

no. m a s = 2 3 4 5 6 7 8  
1 $2^{32}$ 663608941 0.88 0.60 0.80 0.64 0.68 0.61 0.74  
2 $2^{48}$ 43490275647445 0.88 0.71 0.66 0.58 0.73 0.46 0.68  
3 $2^{54}$ 2783377641436325 0.41 0.71 0.42 0.64 0.51 0.61 0.62  
4 $2^{54}$ 2783377640906189 0.87 0.76 0.79 0.78 0.75 0.73 0.69  
5 $2^{54}$ 2783377640450829 0.89 0.84 0.69 0.68 0.72 0.79 0.70  
5 $2^{54}$ 2783377640871525 0.93 0.81 0.81 0.67 0.76 0.73 0.72  

These are examples of LCGs which have been chosen according to the ``golden-section'' proposal [6,46,50] ( $4 a \approx m \xi$ with the golden section number $\xi = (\sqrt{5}-1)/2$ ). A ``classical'' proposal of the latter authors is the generator $LCG(2^{28}$, $41475557, 0, 1)$. LCGs no. 1,3 - 6 were implemented in several versions of C-RAND [93,216,217,218], a package for generating nonuniform random variates. Empirical results for the first generator are given in [12,85,101,118,159]. LCG no. 2 was implemented in [25, V105] and in [199, RAN17].



L'EcuyerLCGs


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

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 [131] he obtained the multipliers $a \le \sqrt{m}$ (for faster implementations) given in Section [*]. 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 [102]. For a similar purpose generator 4.2.1 is applied in [104] 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 [73].

In [144] L'Ecuyer et. al. suggested the following ``good-lattice'' LCGs (see also [132]).

no. $m$ $a\backslash s$ 2 3 4 5 6 7 8
1 $2^{31}-1$ 1385320287 0.767 0.784 0.722 0.809 0.774 0.664 0.676
2 $2^{31}-1$ 41358 0.830 0.704 0.701 0.733 0.665 0.687 0.602
3 $2^{47}-115$ 71971110957370 0.756 0.708 0.688 0.706 0.683 0.762 0.687
4 $2^{47}-115$ -10018789 0.786 0.749 0.773 0.806 0.773 0.744 0.714
5 $2^{63}-25$ 2307085864 0.707 0.713 0.752 0.660 0.803 0.774 0.656

Recent tables of LCGs with different moduli $2^8 \le m \le 2^{128}$ and good lattice structures up to dimension $s = 32$ are given in [141]. The tables below present those LCGs with very large moduli. These LCGs are selected according to the measure $M_i$, $i = 8, 16, 32$ which denotes the minimum of the spectral tests $M_i = \min \{ S_s,\quad 2 \le s \le i\}$. Multiplier 2862933555777941757 also corresponds to the default parameter in the 64-bit LCG (with prime added) implementation in [23]. Empirical results using parameters from [141] are contained in [66,154].

$m$ $a$ $M_8$
$LCG(m, a, 0, 1)$, $m$ prime
$2^{64}-59$ 13891176665706064842 0.74105
  2227057010910366687 0.68377
  18263440312458789471 0.63276
$2^{96}-17 $ 73268029776996600788346432152 0.73790
  24425946592752328169588088988 0.65537
  21759688306225998667176435139 0.67174
$2^{128}-159 $         243267374564284687042667403923350539132 0.74262
  55401819577318168010061270369451294976 0.64466
  119682811202194777305538832478241040430 0.64289
$LCG(m,a,b,0)$, $b$ odd
$2^{64}$ 2862933555777941757 0.75673
  3202034522624059733 0.66164
  3935559000370003845 0.67938
$2^{96}$ 75564983892026345434470042133 0.74760
  41898663544932533964435923957 0.64460
  22104684854187731770179339485 0.65329
$2^{128}$ 47026247687942121848144207491837418733 0.74763
  52583122484843402430317208685168068605 0.70223
  47026247687942121848144207491837523525 0.64332

$m$ $a$ $M_8$
$LCG(m, a, 0, 1)$
$2^{64}$ 1181783497276652981 0.76039
  7664345821815920749 0.67778
  2685821657736338717 0.65961
$2^{96}$ 15616651902759982847603972189 0.74803
  36397579823858211838245240485 0.66550
  11796042828742982733148325285 0.64615
$2^{128}$ 25096281518912105342191851917838718629 0.76598
  23766634975743270097972271989927654085 0.65708
  92563704562804186071655587898373606109 0.63462



MATH

$LCG(m = a^{48}-a^{8}+1, a = 2^{31}, 0, 1)$

This LCG closely approximates the subtract with borrow (SWB) [167] pseudorandom number generator which is implemented in Mathematica (SWB version 7 with period $\approx 10^{445}$ 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 [32,33,136,222,223,224]. Quote[136] : More precisely, the absolute difference between the $u_n$ produced by the approximating 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 $d_s = 1/\sqrt{3}$ for dimensions $s \ge 49$ ( $4.6\; 10^{-10}$ for $s \le 49$). Moreover, certain three dimensional vectors of non-successive values of such generators lie in parallel planes that are at least $1/\sqrt{3}$ apart [136].

Another similar SWB generator given in [167, Vers. 3 Tab. 2] and used as a component of the combined generator proposed in [166] is almost equivalent to $LCG(m = a^{43}-a^{22}+1, a= 2^{32}-5, 0, 1)$. Beyer and spectral tests up to dimensions 50 of this generator are given in [32,224], empirical results in [133]. The lattice structure of the combined generator [166] is examined in [32]. Further empirical results which exhibit defects of AWC and SWB generators are given in [71].



RCARRY

$LCG(m = a^{24}-a^{10}+1, a = 2^{24}, 0, 1)$

Similar as for MATH above, this LCG approximates the SWB generator proposed in [167, Vers. 10 Tab. 2]. A Fortran implementation and timings of RCARRY are given in [107], empirical results in [26,28,232] Quote[136] : The vectors $(u_n, u_{n+10}, u_{n+24})$ produced by that generator lie within a distance of $2^{-24}$ to a pair of planes which are $1/\sqrt{3}$ apart. An improved generator (RANLUX) is proposed in [108,158] and implemented in [25, V115]. Empirical results of different versions of RANLUX are published in [229].


next up previous contents
Next: Parallel LCGs Up: A collection of classical Previous: B    Classical LCGs   Contents
Karl Entacher 2000-06-16