Random numbers arise in computer applications in several different contexts, such as : (i) In the Monte Carlo method to estimate a many-dimensional integral by sampling the integrand. Metropolis Monte Carlo or, more generally, Markov Chain Monte Carlo (MCMC), to which this volume is mainly devoted, is a sophisticated version of this where one uses properties of random walks to solve problems in high dimensional spaces, particularly those arising in statistical mechanics, (ii) In modeling random processes in nature such as those arising in ecology or economics. (iii) In cryptography, one uses randomness to hide information from others. (iv) Random numbers may also be used in games, for example during interaction with the user.
It is only the first class of applications to which this article is devoted, because these computations require the highest quality of random numbers. The ability to do a multidimensional integral relies on properties of uniformity of n-tuples of random numbers and/or the equivalent property that random numbers be uncorrelated. The quality aspect in the other uses is normally less important simply because the models are usually not all that precisely specified. The largest uncertainties are typically due more to approximations arising in the formulation of the model than those caused by lack of randomness in the random number generator.
In contrast, the first class of applications can require very precise
solutions. Increasingly, computers are being used to solve very
well-defined but hard mathematical problems. For example, as
Dirac [1] observed in 1929, the physical laws necessary for
the mathematical theory of a large part of physics and the whole of
chemistry are completely known and it is only necessary to find
precise methods for solving the equations for complex systems. In the
intervening years fast computers and new computational methods have
come into existence. In quantum chemistry, physical properties must
be calculated to ``chemical accuracy'' (say 0.001 Rydbergs) to be
relevant to physical properties. This often requires a relative
accuracy of 
or better. Monte Carlo methods are used to
solve the ``electronic structure problem'' often to high levels of
accuracy [2] (see also articles by Reynolds,
Nightingale, and Kalos in this volume). In these methods one can use
from 
to 
random numbers, and subtle correlations
between these numbers could lead to significant errors.
Another example is from the numerical study of phase transitions. Renormalization theory has proven accurate for the basic scaling properties of simple transitions. The attention of the research community is now shifting to corrections to scaling, and to more complex models. Very long simulations (also of the MCMC type) are done to investigate this effect and it has been discovered that the random number generator can influence the results [3, 4, 5, 6]. As computers become more powerful, and Monte Carlo methods become more commonly used and more central to scientific progress, the quality of the random number sequence becomes more important.
Given that the quality (which we shall define in a moment) of random
numbers is becoming more and more important, the unfortunate fact is
that important aspects of quality are very difficult to prove
mathematically. The best one can do today is test empirically.
But an empirical test is always
finite. We will report here tests on random number streams that are of record
length (up to about numbers). However, they will have to be redone
in a few years with even longer sequences. Also, important
algorithms use random numbers in a way that is hard to encapsulate in
a test for which we know the answer, and so we must resort to general
guidelines on safe ways to use random number generators in practice.
This article constitutes a brief review of recent developments in random number generation. There are several excellent reviews of the older literature. In particular we recommend the reader seriously interested in random number generation read the lengthy introduction in Knuth [7] and the shorter introduction in the 2nd edition of Numerical Recipes [8]. More information can also be found in references [9, 10, 11].
We shall focus here on developments caused by widespread use of parallel computers to perform Monte Carlo calculations. Our impression is that individual users are porting random number generators to parallel computers in an ad hoc fashion, possibly unaware of some of the issues which come to the fore when massive calculations are performed. Parallel algorithms can probe other qualities of random number generators such as inter-process correlation. There is a recent review which covers parallel random number generation in somewhat more depth by Coddington [12]. The interested reader can also refer to [13, 14, 15, 16, 17] for work related to parallel random number generation and testing.
This article is structured as follows. First we discuss the desired properties that random number generators should have. Next we discuss several methods that have been used as generators in particular on parallel computers. Then we discuss testing procedures and show some results of our extensive tests. Quasi random numbers (QRN) have recently been introduced as a way to achieve faster convergence than true random numbers. We briefly discuss these and give some guidelines concerning those applications for which they are likely to be most effective.
We have recently developed a library implementing several of the
parallel random number generators and statistical tests of them on the
most widely available multiprocessor computers. Documentation and
software are available at:
http://www.ncsa.uiuc.edu/Apps/CMP/RNG/RNG-home.html.