Random Numbers

CNCL provides a variety of random number generators, ranging from the very simple linear congruence generator to more sophisticated ones. Also included is a random number generator which reads random data from a file. The generator classes are:

CNLCG

- Linear Congruential Generator

CNMLCG

- Multiplicative Linear Congruential Generator

CNACG

- Additive Congruential Generator

CNFiboG

- Lagged Fibonacci Generator

CNTausG

- Tausworthe Generator

CNFileG

- Data file random number generator

Random numbers are a crucial base of every simulation; most of the pseudo random number generators included in CNCL have their faults and shortcomings. The base random number generators are used by the random distribution classes to generate random numbers with the desired distribution. For futher information refer to the description of the generator you are interested in. Here you can learn something about seed selection in general. The cited references, also the references of the generator-sections, are collected here.

Seed Selection

Due to Lewis and Orav [4] there are some aspects to consider when selecting the seeds for the generators: Ordinarily, the seed value used to initialize a random number generator should not affect the results of the simulation. However, a wrong combination of a seed and a random generator may lead to erroneous conclusions. If the generator has a full period and only one random variable is required, any seed value is as good as any other. However, considerable care is required in selecting seeds for simulations requiring random numbers for more than one variable. Such simulations are called multistream simulations. Some guidelines to follow:

1. If possible, use the same base generator with one seed for all random variables, i.e. successive values of different random variables use successive values of only one base generator. Thus the problem of overlapping streams (see 4.) is avoided.
2. Do not use zero. It would make a multiplicative LCG or a Tausworthe generator stick at zero. According to Knuth [1], the seed for an LCG and its modulus m should be relative prime.
3. Avoid even values. Even values are often as good as odd values. In fact for full period generators, all nonzero seed values are equally good.
4. If distinct streams are needed (see 1.), use nonoverlapping streams. Each stream requires a separate seed. If the two seeds are such that the two streams overlap, there will be a correlation between the streams, and the resulting sequences will not be independent.
5. Reuse seeds in successive replications. If a simulation experiment is replicated several times, the random-number stream need not to be reinitialized, and the seeds left over from the previous replication can continue to be used.
6. Do not use random seeds. Analyst often use random-seed values such as the time of the day. This causes two problems: first, the simulation cannot be reproduced and, second, it is not possible to guarantee that the multiple streams will not overlap. Random-seed selection is therefore not recommended. In particular, do not use successive random numbers obtained from the generator as seeds.

Memory Requirements

LCG

1 longword = 4 bytes

MLCG

2 longwords = 8 bytes

ACG

depends on table size, with default size (55) = 55 + 256 longwords = 1244 bytes

FiboG

102 longwords = 408 bytes

TausG

5 longwords = 20 bytes

For each instance of the generator (on 32bit machines)

Period Length

LCG

2^31- 2

MLCG

2.3 * 10^18

ACG

depends on table size

FiboG

(2^32-1) * 2^96

TausG

-

Evaluation

         | Randomness | Period   | Performance | Memory
         |            | Length   |             | Requirements
   ------|------------|----------|-------------|---------------
   LCG   |    +       |   +      |   +++++     |   +++++
   MLCG  |    ++      |   ++     |   +         |   ++++
   ACG   |    +++     |   1)     |   ++        |   +
   FiboG |    +++++   |   +++++  |   +++       |   ++ 
   TausG |    ++      |   -      |   ++++      |   +++
   ------------------------------------------------------------
   1) depends on table size

Performance evaluation took place on Sun workstations, results for other processors may differ.

Implementation Details

If you are interested in implementation details of the random number generators Press, Vetterling, Teukolsky and Flannery [14], especially chapter 7, may be an interesting first reading. (e.g. Schrage's algorithm is described and a quick and dirty way to convert two longs into one double distributed between zero and 1).

References

[1] Knuth, D.E. Seminumerical Algorithms. 2nd ed., vol.2 of The Art of Computer Programming, Chapter 3, Addison-Wesley, Reading MA, 1981.

[2] Park, S.K., and Miller, K.W., Communications of the ACM, vol.31, pp. 1192-1201, 1988.

[3] Schrage, L., ACM Transactions on Mathematical Software, vol.5, pp. 132-138, 1979.

[4] Lewis, P.A.W, and Orav, E.J. Simulation Methodology forStatisticians, Operations Analysts, and Engineers. vol.1 pp. 88-97, Wadsworth & Brooks/Cole, 1989.

[5] Fishmann, G. and Moore, L. An Exhaustive Analysis of Multiplicative Congruential Random Number Generators with Modulus 2^31-1. SIAM Journal of Scientific and Statistical Computing, 7(1), pp. 24-45, 1985.

[6] L'Ecuyer, P. Efficient and Portable Combined Random Number Generators. Communications of the ACM, vol. 31 (6), pp. 742-774, 1988.

[7] Jain, R. The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling. Chapter 26, John Wiley & Sons, Inc., 1991.

[8] Lehmer, D.H.: Mathematical Methods in Large-Scale Computing Units. Ann. Comput. Lab. Harvard Univ., 26, pp. 141-146, 1951.

[9] Marsaglia, G., Zaman, A. and Tsang, W.-W., Stat. Prob. Lett. 9, 35, 1990.

[10] James, F. A review of pseudorandom number generators. Computer Physics Communication 60, pp. 329-344, North Holland, 1990.

[11] Richter, M. Ein Rauschgenerator zur Gewinnung von quasi-idealen Zufallszahlen fuer die stochastische Simulation. PhD thesis, Aachen University of Technology, 1992.

[12] Tausworthe, R. C. Random Numbers Generated by Linear Recurrence Modulo Two. Math. Comput. 19, pp. 201-209, 1965.

[13] Law, A.M., Kelton, W.D. Simulation Modeling & Analysis. Chapter 7, McGraw Hill, 1991.

[14] Press, W.H., Vetterling, W.T., Teukolsky, S.A., Flannery, B.P. Numerical Recipes in C - The Art of Scientific Computing. 2nd ed., Cambridge University Press, 1994.