A very long period (VLP) pseudorandom number generator for the microcomputer environment

ABSTRACT

This paper examines a pseudorandom number generator based on the generalized feedback shift register (GFSR) algorithm. The rational for the GFSR scheme versus the linear congruential scheme (which is the most commonly implemented) is threefold. The GFSR algorithm can produce streams of pseudorandom numbers of an arbitrarily long period (independent of the word length of the machine), the GFSR algorithm is faster, and the GFSR produces streams which are closer to the uniform distribution (especially for long streams and when the stream is viewed as a set of vectors in n-space). Also included is a discussion of some tests used to verify the uniformity and independence of streams of random numbers. Empirical results of the tests are presented for various pseudorandom number generators, including an implementation of the GFSR scheme, and compared.

REFERENCES

• 1: A. C. Arvillias , D. G. Maritsas, Partitioning the Period of a Class of m-Sequences and Application to Pseudorandom Number Generation, Journal of the ACM (JACM), v.25 n.4, p.675-686, Oct. 1978 [doi>10.1145/322092.322106]
• 2: Banks, J., and Carson, J.S. Ii, Discrete- Event System Simulation, Prentice-Hall, Inc., Englewood Cliffs, NJ, (1984), 256- 291.
• 3: Yap Siong Chua, Analysis and synthesis of feedback queueing models for time-sharing systems., 1973
• 4: Bruce Jay Collings , G. Barry Hembree, Initializing generalized feedback shift register pseudorandom number generators, Journal of the ACM (JACM), v.33 n.4, p.706-711, Oct. 1986 [doi>10.1145/6490.6493]
• 5: T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
• 6: Marsaglia, G., Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. 61 (1968), 25-28.
• 7: Tausworthe, R.C., Random numbers generated by linear recurrence modulo two, Math. Comput. 19 (1965), 201-209.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

General Terms:
Algorithms, Design, Measurement, Performance, Theory