5.6 Implementing Pseudorandom Number Generators

5.6  Implementing Pseudorandom Number Generators

There are a number of practical considerations for implementing pseudorandom number generators.

5.6.1 The number 0

Some pseudorandom number generators can include the number 0 in a sequence of pseudorandom numbers. This happened in our simplistic example of an LCG in Exhibit 5.9, and it will happen with many standard generators if precautions are not taken. The occurrence of a 0 pseudorandom number is a problem for some applications, including any that entail division by pseudorandom numbers.

A solution is to convert any pseudorandom number that equals 0 to a very small number such as .00000001. A similar but more sophisticated solution applicable with LCGs is to set all pseudorandom numbers u[k] equal to z[k]/(η + 1) instead of z[k]/η, while setting u[k] = η/(η + 1) whenever z[k] equals 0. Analogous approaches can be applied with other generators. Another solution is to judiciously select seed values. If an application calls for m pseudorandom numbers, it is easy to check seed values in advance to ensure that the first m pseudorandom numbers generated from those seeds do not include 0. Suitable seed values can be stored for future use. Note that many large-period generators realize 0 multiple times during a single period. Therefore, this solution will only work if the maximum spacing between consecutive 0 values exceeds m. Another solution is to let pseudorandom numbers equal 0, but to incorporate exception-handling code into applications. Finally, we might only use generators that do not include 0 in their full period of numbers.

It is also possible for a generator to produce a pseudorandom number of 1. Such generators are less common and a pseudorandom number of 1 is less likely to crash an application than is 0. However, this problem will arise, and similar solutions to those proposed for 0 apply.

5.6.2 Integer calculations

All the pseudorandom number generators we have considered work with integers z[k] and convert these through division to pseudorandom numbers u[k] only as a last step. The primary reason for this is portability. If intermediate calculations employed noninteger numbers, calculations would involve rounding. Because different computers may round numbers differently, output from a pseudorandom number generator would vary depending upon which computer it was run on. Such uncertain output would make empirical testing of generators machine-dependent. It would render theoretical testing pointless.

Integer calculations solve the problem of rounding, but they pose the equivalent problem of integer overflow. To work properly, a generator’s integer calculations must be exact, without any overflow of numbers. Such overflow might degrade the randomness and/or period of a generator. There are various solutions for this problem, including:

  • employing specialized coding techniques;
  • using generators such as MRGs that employ small integers in all their calculations; and
  • implementing generators using multiple precision.

Optimized algorithms or actual code have been published for many standard random number generators. Whenever possible it is a good idea to base implementations on these.

5.6.3 Implementation verification

Every implementation of a pseudorandom number generator should be verified. This usually takes place when the implementation is first coded, but it should also happen whenever the code is ported to a new computer system. Systems vary with regard to the maximum single-precision integer they may represent without overflow, so an implementation that works on one system may fail on another.

5.6.4 Choosing a generator

The worst way to choose a pseudorandom number generator is by default—simply using one that is packaged with software. Many standard generators, including the widely used LCG [5.14], have periods that are inadequate for somevalue-at-risk calculations. Don’t attempt to design your own generator or to improve upon some standard generator, as results will be unpredictable. The literature documents high-quality generators that have been exhaustively tested and are recommended by experts. Use them.

Despite their limitations, it is best to use linear generators such as LCGs and MRGs. These have been studied for a long time and are well understood. Inversive generators have much appeal, but are still fairly new. Reserve them for verification purposes.

Because of their high periods, MRGs are appealing. MRG [5.18] should work well for manyvalue-at-risk applications. As mentioned previously, its lattice pattern is known to be good for dimensions up to 20. Heuristically, we may expect it to perform well at even higher dimensions. Somevalue-at-risk applications have dimensions in excess of 100. While no linear generator’s lattice pattern has ever been tested for such high dimensions, a generalized MRG recommended by L’Ecuyer (1999) should perform well.