Generalized Feedback Shift Register Pseudorandom Number Algorithm

ABSTRACT

The generalized feedback shift register pseudorandom number algorithm has several advantages over all other pseudorandom number generators. These advantages are: (1) it produces multidimensional pseudorandom numbers; (2) it has an arbitrarily long period independent of the word size of the computer on which it is implemented; (3) it is faster than other pseudorandom number generators; (4) the “same” floating-point pseudorandom number sequence is obtained on any machine, that is, the high order mantissa bits of each pseudorandom number agree on all machines— examples are given for IBM 360, Sperry-Rand-Univac 1108, Control Data 6000, and Hewlett-Packard 2100 series computers; (5) it can be coded in compiler languages (it is portable); (6) the algorithm is easily implemented in microcode and has been programmed for an Interdata computer.

REFERENCES

• 1: R. R. Coveyou , R. D. Macpherson, Fourier Analysis of Uniform Random Number Generators, Journal of the ACM (JACM), v.14 n.1, p.100-119, Jan. 1967 [doi>10.1145/321371.321379]
• 2: KENDALL, M. G., AND SMITH, B. B. Randomness and random samphng numbers J Roy Statist. Soc 10I (1938), 162-164.
• 3: LEwis, P. A W, GOODMAN, A S, AND MILLER, J. M A pseudorandom number generator for the SYSTEM/360 IBM Syst. J. 8, 2 (1969), 136-146.
• 4: M. Donald MacLaren , George Marsaglia, Uniform Random Number Generators, Journal of the ACM (JACM), v.12 n.1, p.83-89, Jan. 1965 [doi>10.1145/321250.321257]
• 5: MARSAGLIA, G. Random numbers fall mainly on the planes. Proc Nat. Acad. Sc~. 61, 1 (Sept 1968), 25-28.
• 6: PAYNE, W. H, AND LEWIS, T. G Conditional bit sampling: Accuracy and speed In Mathematzcal Software, J. R. Rice (Ed), Academic, New York, 1971, pp 331-345.
• 7: TAUSWORTHE, R. C Random numbers generated by linear recurrence modulo two Malh. Compul 19 (1965), 201-209.
• 8: J. P. R. Tootill , W. D. Robinson , A. G. Adams, The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators, Journal of the ACM (JACM), v.18 n.3, p.381-399, July 1971 [doi>10.1145/321650.321655]
• 9: J. P. R. Tootill , W. D. Robinson , D. J. Eagle, An Asymptotically Random Tausworthe Sequence, Journal of the ACM (JACM), v.20 n.3, p.469-481, July 1973 [doi>10.1145/321765.321778]
• 10: John RB Whittlesey, A comparison of the correlational behavior of random number generators for the IBM 360, Communications of the ACM, v.11 n.9, p.641-644, Sept. 1968 [doi>10.1145/364063.364095]
• 11: WHITTLESEY, J. RB., AND GI~IESL, P. Multi-dimensional pseudorandom non-uniformity. Proc. of the UMR-Mervln J Kelly Communication Conference, Oct. 1970, U. of Missouri at Rolla, Rolla, Mo, pp. 15-4-1-15-4-6
• 12: ZIERLER, N. Prm~tive trinomlals whose degree is a Merseime exponent. Inform Contr. 15 (1969), 67-69.
• 13: ZIERLER, N , AND BRILLHART, J. On primitive trmommls (mod 2), II. Inform. Contr. I4 (1969), 566-569

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, Experimentation, Measurement, Performance, Theory