Uniform random number generators: a review <s>  <s> Abstract Much of the informal discussion at the Workshop concerned the merits of different pseudorandom number generators. Here we record some comments based on comparing generators across a wide range of machines. <s> BIB001 </s> Uniform random number generators: a review <s>  <s> Preface 1. Monte Carlo methods and Quasi-Monte Carlo methods 2. Quasi-Monte Carlo methods for numerical integration 3. Low-discrepancy point sets and sequences 4. Nets and (t,s)-sequences 5. Lattice rules for numerical integration 6. Quasi- Monte Carlo methods for optimization 7. Random numbers and pseudorandom numbers 8. Nonlinear congruential pseudorandom numbers 9. Shift-Register pseudorandom numbers 10. Pseudorandom vector generation Appendix A. Finite fields and linear recurring sequences Appendix B. Continued fractions Bibliography Index. <s> BIB002 </s> Uniform random number generators: a review <s>  <s> Stochastic simulation requires a reliable source of randomness. Inversive methods are an interesting and very promising new approach to produce uniform pseudorandom numbers. In this paper, we present evidence that these methods are an important contribution to our toolbox. We survey the outstanding performance of inversive pseudorandom number generators in theoretical and empirical tests, in comparison to linear generators. In addition, this paper contains tables of parameters to implement inversive congruential generators. <s> BIB003 </s> Uniform random number generators: a review <s>  <s> Introduction.- Estimating Volume and Count.- Generating Samples.- Increasing Efficiency.- Random Tours.- Designing and Analyzing Sample Paths.- Generating Pseudorandom Numbers. <s> BIB004
f (s,-I), n 2 1, where the initial state SO E S is called the seed, and f : S + S is the transition function. At step n, the generator outputs u,, = g(sn), where g : S + [0, l] is the output function. The output sequence of the RNG is thus {un, n > 0). The output space could be more general, but we shall assume here that it is the real interval [0, I] . Since S is finite, the sequence must be periodic (possibly after some initial transient). Let p be the period length. Typically, one has p near 15'1, that is, p m 2b if the state is represented over b bits, otherwise there is a waste of computer memory. We now momentarily forget the deterministic nature of the RNG and view the u, as random variables. This could make sense if, for example, the seed SO and/or some parameters of the functions f and g are chosen at random. Define the null hypothesis X0: "The u,, are i.i.d. U(0, 1) (i.e., uniform over the interval (0,l)) random variables". This hypothesis '?-LO means that for each n and t, the vector u, = (UI,..., un+t-1) is uniformly distributed over the t-dimensional unit hypercube It = [O,llt. Of course, this cannot hold, due to the finiteness of S. But for small t, a discretized version of it could hold, as follows. Replace the interval [0, l] by the finite set H,,, = {0,1/m, 2/m, *. . , (m -1)/m} for some large integer m, and suppose that SO is random, uniformly distributed over S, which is assumed to be of cardinality p. Consider the hypothesis 31;: "~0 (and therefore each uLn) is uniformly distributed over the set Zh". The hypothesis 3t', can hold exactly only if p is a multiple of mt . In practice, p is often slightly smaller than a multiple of mt , and 31; can hold approximately. For t such that mt > p, the set Q = {u,,l < n 5 p} is only a small fraction of Z&. In this case, which points of Z!k should be in P? Our opinion is that the points of \1Tr should be uniformly spread over Z&, for all t up to some reasonably large value determined by our analysis capabilities. This is our main criterion for discriminating among generators and for constructing what we call "good ones". As a realistic illustration, let m = 230 and p NN 2210. Then, 31; can hold approximately, if the generator is well designed, for t 5 7. For t > 7, the fraction of Zk that can be covered by 8 is approximately 2-30(t-7). As t increases, this fraction quickly becomes extremely tiny, and nothing can be done against this, aside from increasing p. Note that our reasoning makes sense only if SO is random and if p is huge. One may argue that the points of 8 should look like random points over Z$ instead of being too evenly distributed. But if \E is viewed as a sample space from which points are taken 128 L 'Ecuyer at random by the generator, without replacement, then a superuniform (i.e., very even) distribution of Xl! is justified. In order to make this "uniformity of W' criterion effective from a practical viewpoint, a good theoretical understanding of the structure of XP is required. This is (essentially) what is meant by theoretical analysis of RNGs. After a RNG has been designed and implemented, empirically-minded people will certainly want to apply empirical statistical tests. The number of such tests is unlimited and no amount of empirical testing can ever prove that a given generator is flawless. However, the fact that well-designed RNGs pass most reasonable statistical tests that are usually applied is somewhat reassuring. It makes less likely the possibility of an implementation error or that some major defect has been overlooked. The design and test of a RNG operates much like the design and test of a new car: Even if the car has been constructed based on the most solid theoretical analysis, there will always be people who will want to test it on the road, and for good reasons. Ideally, the statistical tests should be selected in close relation with the target application, that is, be based on a test statistic T that closely mimic the random variable of interest, and where a good approximation of the distribution of T under '& is available. But this ideal is impractical, especially when designing and testing generators for general purpose software packages. In principle, for any RNG, since p < 00, one can easily construct a test that this RNG will fail arbitrarily badly. But if p is large enough, such a test may be impossible to run in "practical" time. A long period, good structure of the points, and passing statistical tests, are not the only required qualities. Simulations involving billions of random numbers are increasingly frequent, and the generator's speed is often a critical factor, regardless of the available computing power. The size of required memory may become important when virtual generators (or substreams) are maintained in parallel. This is required, for example, for proper implementation of certain variance reduction techniques. Portability means that the generator can be implemented easily in a standard high-level language, and produce the same sequence with a wide range of compilers and computers. Repeatability, i.e., being able to reproduce the same sequence all over again, is important for program verification and for variance reduction. This is a major advantage of RNGs over random numbers generated by physical devices. Jumping ahead means the ability to quickly compute, given the current state sn, the state s,,+~ for any large V. This is useful for breaking up the sequence into long disjoint substreams making up virtual generators. The packages of L' Ecuyer and Cot& (1991) and L'Ecuyer and Andres (1997) implement tools to manipulate such substreams. In the remainder of this paper, we survey some of the recent literature on RNGs. The coverage is certainly not exhaustive and is tainted by the author's own interests and opinions. I apologize in advance to those whose interesting papers have not been cited. Further pointers on other aspects or on other RNG classes can be found from the references given here. More extensive coverages of RNGs are given in Eichenauer-Herrmann (1995)) BIB004 , BIB003 ,  BIB002 ) Niederreiter (1995b) , BIB001 Tezuka (1995) , among others. The next section describes RNGs based on linear recurrences in modular integer arithmetic. In Section 4, we survey some developments regarding the combination of such lineartype generators. Section 3 discusses their lattice structure and equidistribution properties. Section 5 mentions classes of nonlinear generators, Section 6 summarizes some work on empirical testing, and Section 7 points to recommended implementations.