Introduction

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.

The National Center for Supercomputing Applications
University of Illinois at Urbana-Champaign

ashoks@ncsa.uiuc.edu

Last modified: September 16, 1997