Some of the well-known fully-worked-out RNG proposals with an obvious or explicit computer implementation.
Bright, H. and R. Enison. 1979. Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography. Computing Surveys. 11(4): 357-370.
"The background of the Lehmer linear congruential algorithms that are in almost universal use for random sequence generation is reviewed; the reasoning is given for choosing the somewhat different Tausworthe linear recurrence (mod 2) type, using the bit selection algorithm of Lewis and Payne; and the initial statistical evaluation is reported on. A review is given of the intuitive process by which the Tausworthe approach, with a generating primitive trinomial of Mersenne prime exponent degree, was chosen."
"We have developed a generator which uses the basic Tausworthe algorithm. . . ." "Lewis-Payne bit selection appears to be superior to decimation: To generate r-bit numbers, each of the r bits is chosen from a different part of the same Tausworthe sequence with a constant gap between bits."
"Our TLP generator uses the trinomial x521 + x32 + 1 to generate 64-bit numbers that are 8-distributed and have good k-distributivity for k > 8. The period of the sequence is 2521 - 1. The LP gap is 52,100."
"Statistical Testing Criteria"
"Other tests have been proposed and used. Lewis and Payne [Lewi73b] ran a conditional bit test, which tested the independence of each bit in a string from the others, as well as a Fourier transform test."
Schrage, L. 1979. A More Portable Fortran Random Number Generator. ACM Transactions on Mathematical Software. 5(2): 132-138.
"A Fortran implementation of a random number generator is described which produces a sequence of random integers that is machine independent as long as the machine can represent all integers in the interval [-2**31 + 1, 2**31 - 1]."
The innovation here is not the RNG, but the method of evaluation, which guarantees that the intermediate values of the generator remain in range.
Wichmann, B. and I. Hill. 1982. Algorithm AS 183. An Efficient and Portable Pseudo-random Number Generator. Applied Statistics. 31: 188-190.
"We claim [our algorithm] is reasonably short, reasonably fast, machine-independent, easily programmed in any language, and statistically sound. It has a cycle length exceeding [6.95 x 1012]."
"The algorithm produces numbers rectangularly distributed between 0 and 1, excluding endpoints." (Actually, zero can occur due to rounding error, but a simple test suffices to tame the situation.)
L'Ecuyer, P. 1988. Efficient and Portable Combined Random Number Generators. Communications of the ACM. 31(6): 742-749, 774.
"ABSTRACT: In this paper we present an efficient way to combine two or more Multiplicative Linear Congruential Generators (MLCGs) and propose several new generators. The individual MLCGs, making up the proposed combined generators, satisfy stringent theoretical criteria for the quality of the sequence they produce (based on the Spectral Test) and are easy to implement in a portable way."
Internally, we have two smaller MLCG's each of which can be implemented easily on 32-bit machines. The internal generators are combined by subtraction to a positive value in the range of one of the generators, then converted to reals by multiplication by 2-31.
"For 32-bit computers, we suggest l=2, m1 = 2147483563, a1 = 40014, m2 = 2147483399 and a2 = 40692." ". . . the combined generator has period . . . 2.30584 x 1018." "It works as long as the machine can represent all integers in the range [-231+85, 231-85]." "Notice that the function will never return 0.0 or 1.0, as long as REAL variables have at least 23-bit mantissa . . . ."
"We performed 21 different tests . . . ."
Park, S. and K. Miller. 1988. Random Number Generators: Good Ones are Hard to Find. Communications of the ACM. 31(10): 1192-1201.
The so-called "Minimal Standard" RNG turns out to be a fairly important reference point, if not an actual standard.
". . . the widespread adoption of good, portable, industry standard software for random number generation has proven to be an elusive goal. Many generators have been written, most of them have demonstrably non-random characteristics, and some are embarrassingly bad."
"To the non-specialist, the construction of a random number generator may appear to be the kind of thing that any good programmer can do easily. Over the years many programmers have unwittingly demonstrated that it is all too easy to 'hack' a procedure that will produce a strange looking, apparently unpredictable sequence of numbers. It is fundamentally more difficult, however, to write quality software which produces what is really desired -- a virtually infinite sequence of statistically independent random numbers, uniformly distributed between 0 and 1. This is a key point: strange and unpredictable is not necessarily random."
The selected design is a multiplicative linear congruential generator (MLCG):
zi+1 = 16807zi mod 231 - 1.
There are two INTEGER and two REAL implementations in easy Pascal. The first two require 46-bit INTEGERS or REALs. Schrange's method is used in the second pair of designs to keep intermediate values within the 32-bit range.
Press, W. and S. Teukolsky. 1989. Quasi- (that is, Sub-) Random Numbers. Computers in Physics. Nov/Dec. 76-79.
"Sometimes we want to pick sample points in an n-dimensional space that are spread out as uniformly as possible. The most obvious case is where we want to integrate a function over n-dimensional space by a Monte Carlo method."
"In the familiar case of uncorrelated points, e.g., those
generated by a good pseudorandom number generator, the fractional
error of the estimated integral will decrease by the equally
familiar
"A simple counterexample is to choose sample points that lie on
a Cartesian grid, and to sample each grid point exactly once . . . .
The Monte Carlo method thus becomes a deterministic quadrature
scheme . . . whose fractional error decreases at least as fast
as
"Sequences of n-tuples that fill n space more uniformly than uncorrelated random points are called quasirandom sequences."
Actual FORTRAN code is given for such a generator.
Macomber, J. and C. White. 1990. An n-Dimensional Uniform Random Number Generator Suitable for IBM-Compatible Microcomputers. Interfaces. 20(3): 49-59.
"[There is] a basic validity problem with mixed congruential RNG's in multidimensional situations [Marsaglia 1968]. Increasing the dimensionality of a hypercube tends to increase the lattice effect. Therefore, what a user believes to be a reliable RNG can become entirely predictable or obviously nonrandom in n-dimensional applications."
"An RNG that overcomes many of the shortcomings of congruential generators is the generalized feedback shift register generator, of GFSR generator [Kennedy 1975; Lewis 1975]."
"The GFSR RNG requires a starting array of randomized binary digits in order to work. To generate these starting numbers, a setup program is required to initialize the generator."
"With the incorporation of Tezuka's test [1987b] within this environment, global n-space uniformity can be guaranteed."
Fushimi, M. 1990. Random number generation with the recursion
Xt = Xt-3p xor Xt-3q. Journal of Computational and Applied Mathematics. 31: 195-118. North-Holland.
"Abstract: A generalized feedback shift register (GFSR) algorithm proposed by Lewis and Payne (1973) uses a primitive trinomial to generate a sequence of pseudorandom numbers. We propose a similar algorithm which uses a primitive polynomial with many non-zero terms, but generates a number as fast as the original GFSR algorithm. Our sequence is guaranteed to be equidistributed in higher dimensions and to have a good autocorrelation property."
"Marsaglia [17] pointed out about 20 years ago that the points in the unit n-cube generated by the Lehmer's linear congruential method lie in a relatively small number of parallel hyperplanes. All sequences generated with recursions of low degree over the finite field have the flaw of sparseness in n-space . . . ."
"We have developed a new method of generating pseudorandom numbers by linear recurrence modulo two. The method uses the recurrence formula
Xt = Xt-3p xor Xt-3q
instead of the formula
Xt = Xt-p xor Xt-q
proposed by Lewis and Payne, where 1 + zq + zp is a primitive polynomial of degree p over the Galois field GF(2) . . . ." "The crucial point in using this generator . . . is the initialization procedure."
"Using the primitive trinomial 1 + z32 + z521, we have performed extensive statistical tests on number sequences generated by our method."
Ripley, B. 1990. Thoughts on pseudorandom number generators. Journal of Computational and Applied Mathematics. 31: 153-163. North-Holland.
"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."
"The idea properties of a good general-purpose pseudorandom number generator are easy to agree but impossible to achieve simultaneously. They include
"It is by now known that well-designed congruential generators have a k-dimensional output which fills a lattice in [0,1)k. All of these examples have adequate lattice structure in up to 8 dimensions [13, Sect. 2.4] and so satisfy the first two requirements, at least weakly. It hardly seems worth searching for 'optimal' multipliers, since most choices are reasonably good. (I find the criteria of Fishman and Moore [3] unreasonably stringent. Generators whose criteria differ by a factor of two are for practical purposes indistinguishable.)"
"Some of these generators (notably Marsg) have a poor two-dimensional discrepancy." "I believe that discrepancy is not a good measure of a pseudorandom number generator, and may not be a good measure for a quasirandom sequence . . . ."
"The alternative family is that of shift-register generators . . . ." "The snag with GFSRs is their initialization." "FORTRAN code is given in the Appendix."
"The reader may already have guessed which generators I actually use. For all but the most demanding problems Marsg suffices. It is simple to program in assembler . . . and easy to check against a double-precision implementation. If any doubt arises from the results of the simulation experiment I use GFSR521 as a cross-check, but have never had cause to doubt Marsg. However, the period of Marsg is beginning to seem too small, and GFSRs have the edge for the future . . . ."
Marsaglia, G. and A. Zaman. 1990. Toward a Universal Random Number Generator. Statistics and Probability Letters. 8: 35-39. North-Holland.
"Abstract: This article describes an approach toward a random number generator that passes all the stringent tests for randomness we have put to it, and that is able to reproduce exactly the same sequence of uniform random variables in a wide variety of computers, including TRS80, Apple, Macintosh, Commodore, Kaypro, IBM PC, AT, PC and AT clones, Sun, Vax, IBM 360/370, 3090, Amdahl, CDC Cyber and even 205 and ETA supercomputers."
This is a combined RNG. One part is a 97-element "lagged-Fibonacci" generator using multiplication. The other part is a linear congruential generator with modulus 169. This is a little more complex, and the write-up a little less clear, than other proposed "standard" designs. Includes Fortran code.
Tezuka, S. and P. L'Ecuyer. 1991. Efficient and Portable Combined Tausworthe Random Number Generators. ACM Transactions on Modeling and Computer Simulation. 1(2): 99-112.
"In this paper, we propose three combined Tausworthe random number generators with period length about 1018, whose k-distribution properties are good and which can be implemented in a portable way. These generators are found through an exhaustive search for the combination with the best lattice structure in GF{2,x}k, the k-dimensional vector space over the field of all Laurent series with coefficients in GF(s). We then apply a battery of statistical tests to these generators for the comprehensive investigation of their empirical statistical properties. No apparent defect was found. In the appendix, we give a sample program in C for the generators."
Collins, J., et. al. 1992. A random number generator based on the logit transform of the logistic variable. Computers in Physics. 6(6): 630-632.
[Note that the term "nonperiodic" in the following paragraph refers to the theoretical situation of mathematical infinite-precision real numbers. In the context of computer floating-point with a limited-precision, no iterative RNG can possibly be "nonperiodic." In fact, we now have the worrisome possibility of multiple cycles of various lengths.]
"A nonperiodic random number generator, which is based on the logistic equation, is presented. A simple transformation that operates on the logistic variable and leads to a sequence of random numbers with a near-Gaussian distribution, is described and discussed. The associated algorithm can be easily utilized in laboratory exercises, classroom demonstrations, and software written for stochastic modeling purposes."
Press, W. and S. Teukolsky. 1992. Portable Random Number Generators. Computers in Physics. 6(5): 522-524.
"Publication of [our] new editions gives us a unique opportunity for confession: There are several sections in the old books that are embarrassingly bad." "Worst among them, we think, is the section on generators of uniform random numbers . . . [we gave] two generators (RAN1 and RAN2) that are at best only mediocre."
"Our new editions, and this column, provide three much better exemplars, named ran0, ran1, and ran2. (Routines in the new editions are named in lower case, in part to distinguish them from old routines.)"
ran0 is the Park-Miller "Minimal Standard" design. ran1 is the same generator with Bays-Durham shuffling. ran2 is the L'Ecuyer "Efficient and Portable" combined design, with added shuffling. A FORTRAN listing for each is given.
Marsaglia, G. 1993. Remarks on Choosing and Implementing Random Number Generators. Communications of the ACM. 36(7): 105-108.
(Comments on Park-Miller "Minimal Standard" designs.)
Marsaglia, G. and A. Zaman. 1994. Some portable very-long period random number generators. Computers in Physics. 8(1): 117-121.
"It is found that a proposed random number generator ran2, recently presented in the Numerical Recipes column . . . is a good one, but a number of generators are presented that are at least as good and are simpler, much faster, and with periods "billions and billions" of times longer. They are presented not necessarily to supplant ran2, but to put it in perspective. Any serious user of Monte Carlo methods should have a variety of random number generators from which to choose. In addition to two specific programs, one in Fortran and one in C, a framework is offered within which the readers can easily fashion their own generators with periods ranging from 1027 - 10101."
Last updated: 2002-01-17