C. More Relevant LCGs

NAG

$LCG(2^{59}, 13^{13}, 0, 123456789 (2^{32}+1))$

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)$

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)$

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 CDC⁶ 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)$

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)$

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

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].