A comparison of the correlational behavior of random number generators for the IBM 360

ABSTRACT

Hutchinson states that the “new” (prime modulo) multiplicative congruential pseudorandom generator, attributed to D.H. Lehmer, has passed the usual statistical tests for random number generators. It is here empirically shown that generators of this type can produce sequences whose autocorrelation functions up to lag 50 exhibit evidence of nonrandomness for many multiplicative constants. An alternative generator proposed by Tausworthe, which uses irreducible polynomials over the field of characteristic two, is shown to be free from this defect. The applicability of these two generators to the IBM 360 is then discussed. Since computer word size can affect a generator's statistical behavior, the older mixed and simple congruential generators, although extensively tested on computers having 36 or more bits per word, may not be optimum generators for the IBM 360.

REFERENCES

• 1: David W. Hutchinson, A new uniform pseudorandom number generator, Communications of the ACM, v.9 n.6, p.432-433, June 1966 [doi>10.1145/365696.365712]
• 2: GORENSTEIN, S. Another pseudorandom number generator. Comm. ACM 9, 10 (Oct. 1966), 711.
• 3: HOLZ, B. W., AND CLARK, C. E. Tests of randomness of the bits of a set of pseudorandom numbers. Published by Operations Research Office (ORO), Dec. 1958; reproduced by ASTIA as AD207553.
• 4: ORCUTT, G. H., GREENBERGER, M., KORBEL, J., AND RIVLIN, A. M. Microanalysis of Socioeconomic Systems. Harper & Row, New York, 1961, App. to Pt. IV, pp. 356-370.
• 5: LEHMER, D. H. Mathematical methods in large scale computing units. In Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, Ann. Comput. Lab: Harvard U. 26 (1951), 141-146.
• 6: WOLD, HERMAN O. A. (Ed.). Bibliography of Time Series and Stochastic Processes. M.I.T. Press, Cambridge, Mass., 1965.
• 7: ANDERSON, R. L. Distribution of the serial correlation coefficient. Ann. Math. Statist. 13, 1 (Mar. 1942), 1-33.
• 8: GREENBERGER, M. An a priori determination of serial correlation in computer generated random numbers. Math. Comput. 15 (1961), 383-389; corrigenda, Math. Comput. 16 (1962), 126, 406.
• 9: 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]
• 10: 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]
• 11: Samuel Gorenstein, Testing a random number generator, Communications of the ACM, v.10 n.2, p.111-118, Feb. 1967 [doi>10.1145/363067.363119]
• 12: TAUSWORTHE, ROBERT C. Random numbers generated by linear recurrence modulo two. Math. Comput. 19 (1965), 201- 209.
• 13: KORN, GRANINO A. Random-Process Simulation and Measurements. McGraw-Hill, New York, 1966, p. 85.
• 14: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
• 15: T. E. Hull , A. R. Dobell, Mixed Congruential Random Number Generators for Binary Machines, Journal of the ACM (JACM), v.11 n.1, p.31-40, Jan. 1964 [doi>10.1145/321203.321208]
• 16: BARNETT, V. D. The behavior of pseudo-random sequences generated on computers by the multiplicative congruential method. Math. Comput. 16 (1962), 63-69.
• 17: CHAMBERS, R. P. Random-number generation on digital computers. IEEE Spectrum 4, 2 (Feb. 1967), 48-56.
• 18: George C. Canavos, A comparative analysis of two concepts in the generation of uniform pseudo-random numbers, Proceedings of the 1967 22nd national conference, p.485-501, January 1967, Washington, D.C., United States [doi>10.1145/800196.806017]
• 19: DOWNHAM, D. Y., AND ROBERTS, F. D. K. Multiplicative congruential pseudo-random number generators. Comput. J. 10, 1 (May 1967), 74-77.
• 20: Martin Greenberger, Method in randomness, Communications of the ACM, v.8 n.3, p.177-179, March 1965 [doi>10.1145/363791.363827]
• 21: ITZELSBERGER, G. Some experiences with the poker test for investigating pseudo-random numbers. In Hollingdale, S. H. (Ed.), Digital Simulation in Operational Research, American Elsevier, New York, 1967, pp. 64-68.

INDEX TERMS

Keywords:
32-bit versus 36-bit word size, IBM 360, autocorrelation function, congruential generators, digital shift-register generators, irreducible polynomials, linear recurrence modulo two, prime numbers, primitive trinomials modulo two, pseudorandom number generators, random numbers, serial correlation, statistical tests for randomness