

INTRODUCTIONS & SURVEYS
In the context of stochastic simulation (i.e. Monte Carlo methods),
the current state of the art in random number generation is reflected
in the proceedings of the Monte Carlo and QuasiMonte Carlo (MCQMC)
conferences, see the website www.mcqmc.org.
The latest issues in this series of proceedings are
Fang, K.T., Hickernell, F.J., and Niederreiter, H. (editor):Monte
Carlo and QuasiMonte Carlo Methods 2000. SpringerVerlag,
New York, 2002.
Niederreiter, H. and Spanier, J. (editor):
Monte
Carlo and QuasiMonte Carlo Methods 1998. SpringerVerlag,
New York, 2000.
There are three books that constitute a "survival kit" for this field,
by Knuth, Niederreiter, and Hörmann, Leydold, and Derflinger. The
"bible", i.e. an alltime classic in the field of random numbers is
Knuth, D.E.: The
Art of Computer Programming, volume 2: Seminumerical Algorithms.
AddisonWesley, Reading, MA, 3rd edition, 1997.
Knuth's book is extremely rich in information but requires good knowledge
of mathematics, in particular number theory. I would not recommend this
book as first reading for practitioners. The following monograph contains
a comprehensive discussion of the theoretical assessment of random number
generators and a valuable list of references. Readers should be prepared
for a text in pure mathematics, in particular number theory and algebra
(theory of finite fields).
As Knuth's book, Niederreiter's excellent monograph is an important reference
in this field.
Niederreiter, H.: Random Number Generation and QuasiMonte
Carlo Methods. SIAM, Philadelphia, 1992.
The monograph on nonuniform random variate generation,
Hörmann, W., Leydold, J. and Derflinger, G.: Automatic
Nonuniform Random Variate Generation. SpringerVerlag,
New York, 2004,
will be very helpful for all those who need nonuniform random numbers.
The following papers of Pierre L'Ecuyer survey many of the basic concepts
and results of random number generation, most of it readable by nonspecialists.
I strongly recommend to visit Pierre's
webpage for his latest results.
L'Ecuyer, P.: Uniform random number
generation. Ann. Oper. Res., 53: 77120, 1994.
L'Ecuyer, P.: Random number generation. In Jerry Banks,
editor(s), The
Handbook of Simulation, pp. 93137. Wiley, New York,
1998.
L'Ecuyer, P.: Random
number generation. Draft for a chapter of the forthcoming
Handbook of Computational Statistics, J. E. Gentle, W. Haerdle,
and Y. Mori, eds., SpringerVerlag, 2004.
his paper of mine was written for practitioners. It explains the state
of the art to assess random number generators and gives pointers
to implementations of the latest advances in generating random numbers
up to 1999.
Hellekalek, P.: Good random number generators are (not so)
easy to find. Mathematics and Computers in Simulation, 46: 485505,
1998.
The first twenty pages of the following contribution deal with the importance
of theoretical (i.e. a priori) testing of RNGs, illustrated by examples,
and written in a language easily understood by practitioners.
Hellekalek, P.: On the assessment of random and quasirandom
point sets. In Hellekalek, P. and Larcher, G., editor(s), Random
and QuasiRandom Point Sets of Lecture Notes in Statistics.
SpringerVerlag, New York, 1998.
If you are looking for a compact survey of the theoretical properties
of random number generators, with a special interest in nonlinear types,
then an excellent source is
Niederreiter, H.: New developments in uniform pseudorandom
number and vector generation. In Niederreiter, H. and Shiue,
P.J.S., editor(s), Monte
Carlo and QuasiMonte Carlo Methods in Scientific Computing,
volume 106 of Lecture Notes in Statistics. SpringerVerlag, Heidelberg
New York, 1995.
The following paper contains a concise survey of the performance of inversive
random number generators in theoretical and empirical tests, as well as
tables of parameters to implement inversive generators.
Hellekalek, P.: Inversive
pseudorandom number generators: concepts, results, and links. In
Alexopoulos, C. and Kang, K. and Lilegdon, W.R. and Goldsman, D.,
editor(s), Proceedings of the 1995 Winter Simulation Conference,
pp. 255262. , 1995.
Abstract available.
For those who want to understand the goals and the limitations of empirical
testing of random number generators (and why undefined notions like "independence
of random numbers", and "statistical properties of numbers" should be avoided),
there is a Master's thesis dedicated to these questions, written by Stefan
Wegenkittl. It also contains comprehensive results on Marsaglia's Mtuple
test for inversive and linear generators.
Wegenkittl, S.: On
Empirical Testing of Pseudorandom Number Generators.
In De Pietro,G. and Giordano, A. and Vajtersic, M. and Zinterhof,
P., editor(s), Proceedings of the international workshop Parallel
Numerics '95. CEIPACT Project, WP5.1.2.1.2. , 1995.
Stefan has recently published a very interesting addition to Maurer's universal
statistical test for random bit generators, see
Wegenkittl, S.: Entropy Estimators and Serial Tests
for Ergodic Chains. IEEE Transactions on Information Theory,
47: (6) 24802489, 2001.
Additional interesting surveys of the field are given in the papers
below, sorted by date of publication. The surveys of Anderson, Marsaglia,
and L'Ecuyer are of particular interest for practitioners.
Marsaglia, G.: A current view of random number generators.
In Billard, L., editor(s), Computer Science and Statistics: The Interface,
pp. 310. Elsevier Science Publishers B.V., Amsterdam, 1985.
Anderson, S.L.: Random number generators on vector supercomputers
and other advanced architectures. SIAM Rev., 32: 221251,
1990.
Eddy, W.F.: Random number generators for parallel processors.
J. Comp. Appl. Math., 31: 6371, 1990.
L'Ecuyer, P.: Random numbers for simulation. Comm. ACM, 33:
8597, 1990.
L'Ecuyer, P.: Random number generation. In Jerry Banks,
editor(s), The
Handbook of Simulation, pp. 93137. Wiley, New York,
1998.
Ripley, B.D.:Thoughts on pseudorandom number generators.
J. Comput. Appl. Math. , 31: 153163, 1990.
MATHEMATICAL FOUNDATIONS AND PHILOSOPHY
How to define the notion of "a (finite) sequence of random numbers"?
Knuth describes the problem as this:
The mathematical theory of probability and statistics carefully
sidesteps this question; it refrains from making absolute statements,
and instead expresses everything in terms of how much probability
is to be attached to statements involving random sequences of events.
The axioms of probability theory are set up so that abstract probabilities
can be computed readily, but nothing is said about what probability really
signifies, or how this concept can be applied meaningfully to the actual
world.
The following papers and textbooks propose notions of randomness different
from Kolmogorov's:
Chaitin, G.J.: Randomness and mathematical proof. Sci.
Amer., 232: 4752, 1975.
Compagner, A.: Definitions of randomness.
Am. J. Phys., 59: 700705, 1991.
Kac, M.: What is random?. American Scientist,
71: 405406, 1983.
Knuth, D.E.: The
Art of Computer Programming, volume 2: Seminumerical Algorithms.
AddisonWesley, Reading, MA, 2nd edition, 1981.
Schnorr, C.P.: Zufälligkeit und Wahrscheinlichkeit, volume
218 of Lecture Notes in Math.. Springer, Berlin, 1971.
The theory of uniform distribution of sequences, a sub field of numbertheory,
is not concerned with randomness but provides highly useful tools to construct
theoretical "figures of merit" for random number generators. The keyword
is "discrepancy of point sets and sequences". For an excellent introduction
to this field, see
Kuipers, L. and Niederreiter, H.: Uniform Distribution of
Sequences. John Wiley, New York, 1974.
Even the spectral test is nothing else than a measure of uniform distribution,
as I have shown in my survey
Hellekalek, P.: On the assessment of random and
quasirandom point sets. In Hellekalek, P. and Larcher, G.,
editor(s), Pseudo and QuasiRandom Point Sets of Lecture Notes in Statistics.
SpringerVerlag, New York, 1998.
The algebraic background of random number generation (keyword: "arithmetics
in finite fields"; think of shift register types of generators or of inversive
generators) can be found in the comprehensive monograph
Lidl, R. and Niederreiter, H.: Finite
fields. AddisonWesley, Reading, Mass., 1983.
There is a monograph on the Monte Carlo method that will certainly become
a standard reference, in particular among practitioners,
Fishman, G.S.: Monte
Carlo: Concepts, Algorithms, and Applications. SpringerVerlag,
New York, 1996.
The same holds for the monograph on nonuniform random variate generation,
Hörmann, W., Leydold, J. and Derflinger, G.: Automatic
Nonuniform Random Variate Generation. SpringerVerlag, New
York, 2004.
SIMULATION
LINEAR GENERATORS
This type of generator is the bestknown (and analyzed) approach
to produce uniform random numbers. The spectral test (see our
Spectral Test Server) is a very efficient figure of merit to
assess linear generators like the linear congruential generator
(LCG) or its generalization, the multiple recursive generator (MRG).
There are many related methods. All these basic concepts are discussed
in
L'Ecuyer, P.: Random number generation. In
Jerry Banks, editor(s), The Handbook of Simulation, pp. 93137.
Wiley, New York, 1998.
Pierre L'Ecuyer is the leading specialist for this type of generators. He
has driven the spectral test to new limits in efficiency, on the basis of
the theoretical background provided by people like Ulrich Dieter, see
Dieter, U.: How to calculate shortest vectors in a lattice.
Math. Comp., 29: 827833, 1975.
and Donald Knuth (see his famous monograph cited above).
Among linear type generators, Matsumoto's twisted generalized feedback
register generators (tGFSR) stand out. His "Mersenne Twister" is the current
World Champion among random number generators, see
Matsumoto, M. and Kurita, Y.: Twisted GFSR generators.
ACM Trans. Model. Comput. Simul., 2: 179194, 1992.
Matsumoto, M. and Kurita, Y.: Twisted GFSR generators II.
ACM Trans. Model. Comput. Simul., 4: 254266, 1994.
Matsumoto, M. and Nishimura, T.: Mersenne Twister: A
623dimensionally equidistributed uniform pseudorandom number
generator . ACM Trans. Modeling and Computer Simulation,
8: 330, 1998.
A rather comprehensive collection of widlyused and also some exotic
linear random number generators is due to my former student Karl
Entacher. It is available online
from our server. Karl's collection contains not only the parameters
of these generators, but also the values of extensive spectral tests.
SIMULATION
NONLINEAR CONGRUENTIAL GENERATORS
Nonlinear random number generators constitute an important addition
to the arsenal of algorithms for stochastic simulation practice.
Their properties are radically different from those of linear generators.
There are several theoretical and some practical advantages for
nonlinear generators, like the absence of any lattice structure,
but (currently) also two disadvantages: speed and period length.
Nevertheless, these algorithms merit closer consideration in theory
and in practice. The main designers of these algorithms are Harald
Niederreiter and Jürgen EichenauerHerrmann. The most important
nonlinear concept up to now is the socalled inversive congruential
generator (ICG), due to EichenauerHerrmann and Lehn. A survey of
inversive random number generators is given in
Hellekalek, P.: Inversive
pseudorandom number generators: concepts, results, and links.
In Alexopoulos, C. and Kang, K. and Lilegdon, W.R. and Goldsman,
D., editor(s), Proceedings of the 1995 Winter Simulation Conference,
pp. 255262. , 1995.
Abstract available.
This paper contains a concise discussion of the main concepts of generating
and testing inversive random numbers and a comparison to linear generators.
Recently, Harald Niederreiter and Igor Shparlinski have made important advances
in the theoretical study of nonlinear algorithms. The following papers are
good starting points to learn about these developments,
Niederreiter, H. and Shparlinski, I.~E.: On the distribution
and lattice structure of nonlinear congruential pseudorandom numbers.
Finite Fields and Their Applications, 5: 246253, 1999.
Niederreiter, H. and Shparlinski, I.~E.: On the distribution of pseudorandom
numbers and vectors generated by inversive methods. Appl.
Algebra Engrg. Comm. Comput., 10: 189202, 2000.
Niederreiter, H. and Winterhof, A.: Incomplete exponential
sums over finite fields and their applications to new inversive
pseudorandom number generators. Finite Fields and Their
Applications, 93: 387399, 2000.
The following Master's Thesis written at pLab gives a graduate level introduction
to inversive generators.
Weingartner, A.: Nonlinear
congruential pseudorandom number generators. Master's thesis,
University of Salzburg, 1994.
Abstract available.
The comprehensive survey of Niederreiter
Niederreiter, H.: New developments in uniform pseudorandom
number and vector generation. In Niederreiter, H. and Shiue,
P.J.S., editor(s), Monte Carlo and QuasiMonte Carlo Methods in
Scientific Computing, volume 106 of Lecture Notes in Statistics.
SpringerVerlag, Heidelberg New York, 1995.
covers not only inversive, but also other nonlinear methods to produce random
numbers. This paper concentrates on theoretical results. It contains a wealth
of references.
EichenauerHerrmann, his wife Eva Herrmann, and my former student Stefan
Wegenkittl survey the present state of theoretical results for inversive
and quadratic generators in
EichenauerHerrmann, J. and Herrmann, E. and Wegenkittl, S.:
A survey of quadratic and inversive congruential pseudorandom
numbers. In Proceedings of the Second International Conference
on Monte Carlo and QuasiMonte Carlo Methods in Scientific Computing,
Salzburg, July 912, 1996 of Lecture Notes in Statistics. SpringerVerlag,
New York, 1997.
Many of these results remain state of the art.
CRYPTOGRAPHICAL GENERATORS
Good starting points for mathematicians are the survey paper
of Lagarias
Lagarias, J.C.: Pseudorandom Numbers. Statistical
Science, 8: 3139, 1993.
and the classical paper on cryptographical random bit generators by Blum
and Micali
Blum, M. and Micali, S.: How to generate cryptographically
strong sequences of pseudorandom bits. SIAM Journal of
Computing, 13: 850864, 1984.
Oded Goldreich's monograph might become a classic on pseudorandomness in
cryptography, Michael Luby's book has become one already,
Goldreich, O.: Modern Cryptography,
Probabilistic Proofs and Pseudorandomness. Springer Verlag, Berlin,
1999.
Luby, M.: Pseudorandomness and Cryptographic Applications.
Princeton Computer Science Notes, 1996.
Monte Carlo random number generation is different from cryptographical applications.
Hugo Krawczyk has shown that all polynomial generators (like linear congruential
generators, etc.) are predictable, see
Krawczyk, H.: How to predict congruential generators.
In Brassard, G., editor(s), Advances in CryptologyCRYPTO'89, volume
435 of Lecture Notes in Computer Science, pp. 138153. SpringerVerlag,
1990.
The bestknown statistical test in the context of cryptographical generators
is Maurer's Universal Statistical Test
Maurer, U.: A Universal Statistical Test for Random
Bit Generators. J. Cryptology, 5: 89105, 1992.
see also Wegenkittl's extension
Wegenkittl, S.: Entropy Estimators and Serial Tests
for Ergodic Chains. IEEE Transactions on Information Theory,
47: (6) 24802489, 2001.
Many other references and a concise discussion of practically all relevant
concepts are contained in the fine book by Menezes, van Oorschot,
and Vanstone, and in Bruce Schneier's monograph for practitioners
in (mathematical) cryptography, Menezes, A.~J. and van Oorschot, P.~C.
and Vanstone, S.A.: Handbook
of Applied Cryptography. CRC Press, Boca Raton, 1997.
Schneier, B.: Applied
Cryptography. Wiley, New York, Second edition, 1996.
back to the top
Research supported by and
Jubiläumsfond
der OeNB


