Introduction

The present paper contains a collection of linear pseudorandom number generators (PRNGs) that were implemented in commercial software, used in applications, and some of which have extensively been tested. It also demonstrates shortcomings of linear congruential generators in parallel environments, and provides a voluminous bibliography on (linear) random number generation.

Summary of PRNGs used from the 1960s to 1980s are given in Kennedy and Gentle [120], Park and Miller [189, Sect. 4] and Dudewicz and Ralley [51, Chapter. 1]. For classical publications on random number generation see [51,109,179]. Surveys on pseudorandom numbers are contained in [73,85,91,107,126,129,132,134,139,164,182,184,186,203,222], surveys for parallel PRNGs in [8,18,19,27,53,54,215,170,171]. For World-Wide-Web sites which provide interesting informations on random number generation see the The WWW Virtual Library: Random Number Generation and Monte Carlo Methods.

Linear congruential generators (LCGs) are the best analyzed and most widely used (uniform) PRNGs. LCGs allow an easy (number-) theoretical analysis based on the lattice structure formed by $s$-dimensional vectors ${\bf u}_n^{\scriptscriptstyle (s)} = (u_n,\ldots,u_{n+s-1}), n\ge 0$ of all generated uniforms $u_n$. The quality of LCGs heavily depends on the coarseness of the lattice [126]. In order to find ``optimal'' parameters for LCGs, several ratings of the lattice structure have been proposed. The most popular measure is the spectral test which gives the maximal distance $d_s$ between adjacent parallel hyperplanes, the maximum being taken over all families of parallel hyperplanes that cover all vectors ${\bf u}_n^{\scriptscriptstyle (s)}$ (see [36,126,131]). In other words, $d_s$ determines the maximal size of empty slices (without points ${\bf u}_n^{\scriptscriptstyle (s)}$) within $[0,1[^s$. The smaller $d_s$ the more uniform is the sample space of the points.

Section contains a collection of many classical- and recent LCGs. References concerning theory, empirical properties, implementations, and literature are given. The references are supplemented by quotations (Quote [reference]) of several authors which point out the basic properties of generators in an essential way or give critical remarks. We further present two ``fingerprints'' of LCGs: a zoom into the two- or three-dimensional unit cube which exhibits their lattice structures and results of a normalized spectral test $S_s := d^*_s / d_s$, $2 \le s \le 8$, for which $0 \le S_s \le 1$. This figure of merit should be viewed as a correlation measure (values near 1 imply a ``good'' lattice structure, whereas values near 0 exhibit strong correlations within the generated sequence). The constants $d^*_s$ are absolute lower bounds on $d_s$, see [126, p. 105], [73, Sect. 7.7] and [141] for certain bounds $d^*_s$ for $s > 8$. In Subsection A the reader may imagine the coherence of bad normalized spectral tests and their effects to the lattice with some examples of unreasonable LCGs. More details on the spectral test can be found in Subsection .

In Section we use the spectral test to study the applicability of LCGs in parallel simulation environments. The standard technique to get parallel streams of random numbers is to split a sequence of PRNs into suitable subsequences. The spectral test offers an easy method to study correlations within and between common parallel streams. We have analyzed lagged subsequences with small lags for almost all LCGs from Section . Additionally we used the spectral test to exhibit the well known long-range correlations between consecutive blocks generated from linear generators. Many different subsequences may occur in serial simulations as well. Our results clearly show that LCGs proposed due to their good lattice structures have to undergo a seperate subsequence analysis as well.

In Section and we consider multiple recursive generators and combined linear congruential generators. These types of generators can be implemented very efficiently and still offer long periods. Similar to LCGs, the set of all s-dimensional vectors ${\bf u}_n^{\scriptscriptstyle (s)}$ of multiple recursive generators form lattice structures. Moreover, combined LCGs are equivalent to LCGs with high periods, and they provide some interesting splitting properties to get ``independent'' parallel streams of PRNs. Finally, in Section we provide references for further linear methods and a unified framework.

Our spectral tests have been calculated using the dual lattice approach of Dieter [47] and a Mathematica implementation of the Fincke-Pohst algorithm for finding the shortest vector in a lattice by Wilberd van der Kallen., University of Utrecht, Netherlands.