| <- HREF="node9.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments
· Archive
· Search
of random integers using the relation
where a is known as the multiplier, M is the modulus, and c is an
additive constant that may be set to zero.
The parameters (a,c,M) must be chosen carefully to ensure a large
period and good uniformity and randomness properties.
The maximum period is M for suitably chosen parameters (M-1 if c=0)
[1].
Standard random number generators return a floating point number 
in the interval [0,1), which can be obtained by dividing
by M.
LCGs work very well for most applications but are known to have some
major defects.
The main problem is that the least significant bits of the numbers produced
are correlated, and
a ``scatter-plot'' of ordered tuples (
, ...) of
random floating point numbers plotted in the unit hypercube shows regular
lattice structure [2, 27, 32, 33, 7].
This problem becomes worse in higher dimensions, which may affect some
high-dimensional simulations.
The problem of lattice structure can be quantified using the Spectral
Test [1].
Examples of LCGs with good parameters that perform well in the Spectral Test
are given in Refs. [1, 40, 15, 41].
Another problem is that many commonly-used LCGs (including DRAND48 and RANF) use a modulus M that is a power of 2, since it is fast and convenient to implement this on a computer. However this approach produces highly correlated low-order bits [1, 4, 7], as well as long-range correlations for intervals that are a power of 2 [8, 11, 34, 35, 36]. This can cause problems for certain types of simulations, for example when using a hypercubic grid with a size that is a power of 2, or for applications that expect the lower-order bits to be random. To avoid these problems, it is best to use a modulus that is prime rather than a power of 2, however for many applications requiring single-precision floating point pseudo-random numbers (for which the low-order bits are irrelevant), DRAND48 and RANF are quite adequate, and are often useful for checking the results obtained using other generators.
The effects of these regularities can be decreased by increasing the precision of the generators [2], for example by using 64-bit rather than 32-bit numbers. However there are practical limits to this approach - if M is greater than machine precision, then much slower multi-precision arithmetic must be used, so in practice the precision cannot be made arbitrarily large. This means that 48-bit and 64-bit LCGs can be quite slow on 32-bit computers, however many high-performance computers now use 64-bit processors, which should become standard in the near future. In that case, the speed of these generators is not a problem for most applications.
Note that for 32-bit integers the period of these generators
is at most
, or of order
.
On current processors capable of
floating point operations per second, this period can be exhausted
in seconds, so higher precision (48-bit or more) generators should
be used. For long simulations on high-performance computers,
even 48-bit generators may have too small a period.
Despite their known problems, large precision LCGs with well-chosen parameters appear to work very well for all known applications, at least on sequential computers. However we will see later that there are problems with implementations of LCGs on parallel computers if the modulus is a power of 2.
Multiple recursive generators (MRG) [1, 5, 6, 41], generalize LCGs by using a recurrence of the form
for a given value of k. Choosing k > 1 will increase the time taken to generate each number, but will greatly improve the period and randomness properties of the generator [6, 41]. Some practical implementations have been provided for k=2 [41].
| <- HREF="node9.html" Prev | Index | Next -> |
NHSE ReviewTM: Comments
· Archive
· Search
