- Home - Contact - Impressum

On this page, you will find information on uniform random number generators (RNGs). We will not (yet) discuss cryptographic generators, nor non-uniform random numbers. For those two topics and for code for RNGs, we refer to our Links and Software pages.

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 non-deterministic algorithms. Deterministic RNGs are usually called pseudo-random 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 best-known 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 Li-Yuan 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 state-of-the-art 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.
Generator LCG ICG EICG
Parameters X X X
Theoretical Properties -,+ + +
Empirical Performance -,+ + +
Implementation X X X
Examples X X X
Literature X X X

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 mega-city, 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