ABOUT
THIS PAGE
On this page, you will find information on uniform random number
generators (RNGs). We will not (yet) discuss cryptographic generators,
nor nonuniform random numbers. For those two topics and for code
for RNGs, we refer to our Links
and Software
pages.
This page has been written by Peter
Hellekalek.
GENERAL
REMARKS
Uniform RNGs produce numbers with certain distribution properties.
Roughly speaking, these numbers should behave similar to realizations
of independent, identically distributed random variables.
We may distinguish between hard and software RNGs and, among the
algorithms, between deterministic and nondeterministic algorithms.
Deterministic RNGs are usually called pseudorandom number generators.
We will simply use the term "RNG" for all of those. Links
to some hardware RNGs are to be found via our Links
page.
Every RNG has its deficiencies. No RNG is appropriate for all tasks.
For example, several good RNGs from the toolbox of stochastic simulation
are unsuited for cryptographical applications, because they produce
predictable output streams. On the other hand, cryptographic RNGs
are usually (but not always) too slow for doing Monte Carlo simulations.
A good RNG has been thoroughly analyzed theoretically and is backed
by convincing practical evidence like extensive statistical testing.
In stochastic simulation, in order to verify our simulation results,
we should be able to choose from a whole arsenal of widely different
RNGs. The reason behind this argument is the possibility that the
intrinsic structure of our RNG might interfere with our simulation
problem and yield wrong results.
There are two big families of RNGs, linear generators and nonlinear
ones. Cryptographers stay away from the linear algorithms because
of predictability reasons, but in Monte Carlo simulations, linear
RNGs are the bestknown and most widely available ones. If one has
to generate huge samples of random numbers as efficiently as possible,
then one will use linear RNGs like the extremely fast and reliable
RNGs available from Makoto Matsumoto, see TT800
and the Mersenne Twister,
or the (single or combined) multiple recursive generators
studied and implemented by Pierre L'Ecuyer,
see his publications page,
or one of LiYuan Deng's huge RNGs.
.
Sometimes, you will run into trouble with linear RNGs, because
those algorithms produce linear point structures in every dimension
and this fact may interfere with your simulation problem. For this
reason, nonlinear generators have been introduced. In general, they
are much slower than linear generators of comparable size (by a
factor of, say 5 to 10), but they allow you to use larger samples.
At present, there is no equivalent to the huge linear generators
of Matsumoto and L'Ecuyer available in the nonlinear family, with
one notable exception. You may use AES as a highly efficient nonlinear
RNG with a huge period. Together with Stefan Wegenkittl, I have
submitted AES to stateoftheart statistical tests. AES has passed
with flying colours, see our recent ACM
TOMACS article titled "Empirical Evidence Concerning AES".
GENERATORS
In the pLab project we have investigated the most promising
nonlinear type, inversive
RNGs (keywords: ICG, EICG). These generators have properties that
differ strongly from those of traditional generators like
linear generators (keyword: LCG), or from shift register generators.
Implementations in C of inversive and also of linear RNGs are available
on our Software
page. Appropriate parameters for ICGs are availabe from the Winter
Simulation Conference 1995 survey paper by Peter Hellekalek
and in the form of extensive tables
of parameters.
The following table is an index to the available information.
FURTHER
INFORMATION
Further information on multiple
recursive generators (MRGs) and combined
LCGs and a basic
introduction in "linear" methods in general is available,
see also the survey
paper written for practitioners.
Randomness in Practice: Travelling around in Buenos Aires, Argentina, comes close to a random walk, even for local people.
In order to find your way around this megacity, there now is
viaja fácil, a website that will tell you how to get from
point A to point B. Highly recommended!
If you need code for RNGs, please see our Software
page.
back to the top
Research supported by and
Jubiläumsfond
der OeNB
