|
 |
 |
 |
||||||||||||||||||||||||||||||||||||||||||||||
|
 ABOUT THIS PAGE 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. This page has been written by Peter Hellekalek.
GENERAL
REMARKS 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 The following table is an index to the available information.
FURTHER
INFORMATION 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.
|
|
|||||||||||||||||||||||||||||||||||||||||||||
 |
 |
