Introduction

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 -dimensional vectors
of all generated uniforms .
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 between
adjacent parallel hyperplanes, the maximum being taken over all families of
parallel hyperplanes that cover all vectors
(see [36,126,131]).
In other words,
determines the maximal size of empty slices (without points
) within . The smaller
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
, ,
for which
. 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 are absolute lower bounds on , see
[126, p. 105], [73, Sect. 7.7] and [141] for
certain bounds for .
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 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.