NHSE Review^TM 1996 Volume Second Issue

Random Number Generators for Parallel Computers

| <- HREF="node4.html" Prev | Index | Next -> |
NHSE Review^TM: Comments · Archive · Search

Requirements for Sequential Random Number Generators 

Ideally a pseudo-random number generator would produce a stream of numbers that

1. are uniformly distributed,
2. are uncorrelated,
3. never repeats itself,
4. satisfy any statistical test for randomness,
5. are reproduceable (for debugging purposes),
6. are portable (the same on any computer),
7. can be changed by adjusting an initial ``seed'' value,
8. can easily be split into many independent subsequences,
9. can be generated rapidly using limited computer memory.

In practice it is impossible to satisfy all these requirements exactly. Since a computer uses finite precision arithmetic to store the state of the generator, after a certain period the state must match that of a previous iteration, after which the generator will repeat itself. Also, since the numbers must be reproduceable, they are not truly random, but generated by a deterministic iterative process, and therefore cannot be completely uncorrelated.

For practical purposes, we require that the period of repetition of the sequence be much larger than the number of pseudo-random numbers that might be used in any application, and that the correlations be small enough that they do not noticeably affect the outcome of a computation. The first requirement can be determined fairly easily, knowing the power of the computer to be used. The second is extremely difficult to ascertain, and will generally be application-dependent.

It has often been the case that the speed of random number generators has been overly emphasized, to the detriment of the quality of the generators. A fast generator requires a minimal number of very simple operations, and it is this simplicity that often leads to problems with the quality of such generators. For most applications the speed of a random number generator is not even a concern, since the amount of time spent generating the random numbers is insignificant compared to the rest of the calculation. Users who yearn for super-fast random number generators usually have applications that spend most of their time generating random numbers, and require a huge number of them. These types of applications are often the ones that are most sensitive to the quality of the generator, in which case it would seem prudent to sacrifice a little speed for much better randomness properties. In using a random number generator, it's usually better to be slow than sorry.

The speed of a random number generator can usually be increased by allowing the routine to return an array of values, rather than a single value. This is clearly advantageous for a vector or parallel implementation, however it is also usually true for a sequential implementation, since it amortizes the cost of the function call to the random number generator.

Copyright © 1996

| <- HREF="node4.html" Prev | Index | Next -> |
NHSE Review^TM: Comments · Archive · Search