Some New Results in Pseudo-Random Number Generation

ABSTRACT

Pseudo-random number generators of the power residue (sometimes called congruential or multiplicative) type are discussed and results of statistical tests performed on specific examples of this type are presented. Tests were patterned after the methods of MacLaren and Marsaglia (M&M). The main result presented is the discovery of several power residue generators which performed well in these tests. This is important because, of all the generators using standard methods (including power residue) that were tested by M&M, none gave satisfactory results. The overall results here provide further evidence for their conclusion that the types of tests usually encountered in the literature do not provide an adequate index of the behavior of n-tuples of consecutively generated numbers. In any Monte Carlo or simulation problem where n supposedly independent random numbers are required at each step, this behavior is likely to be important. Finally, since the tests presented here differ in certain details from those of M&M, some of their generators were retested as a check. A cross-check shows that results are compatible; in particular, if a generator failed one of their tests badly, it also failed the present author's corresponding test badly.

REFERENCES

• 1: J. L. Allard , A. R. Dobell , T. E. Hull, Mixed Congruential Random Number Generators for Decimal Machines, Journal of the ACM (JACM), v.10 n.2, p.131-141, April 1963 [doi>10.1145/321160.321163]
• 2: 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]
• 3: -- AND --. Random number generators. SIAM Rev. 4 (1962), 230-254.
• 4: INTERNATIONAL BUSINESS MACHINES CORPORATION. Random Number Generation and Testing. Ref. Manual C20-8011, IBM Corp., New York, 1959.
• 5: JOHNSON, D.L. Generating and testing pseudo-random numbers on the IBM Type 701. Math. Tables Aids Comput. 10 (1956), 8-13.
• 6: JUNCOSA, M.L. Random number generation on the BRL high-speed computing machines. Rep. No. 855, Ballistics Research Laboratories, Aberdeen Proving Ground, Md., 1953.
• 7: Jack Moshman, The Generation of Pseudo-Random Numbers on a Decimal Calculator, Journal of the ACM (JACM), v.1 n.2, p.88-91, April 1954 [doi>10.1145/320772.320775]
• 8: A. Rotenberg, A New Pseudo-Random Number Generator, Journal of the ACM (JACM), v.7 n.1, p.75-77, Jan. 1960 [doi>10.1145/321008.321019]
• 9: TAUSSKY, O., AND TODD, J. Generation and testing of pseudo-random numbers. In Symposium on Monte Carlo Methods, Mayer, H. A. (Ed.), Wiley, New York, 1956, pp. 15-28.
• 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: 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]
• 12: SMIRNOV, N. Table for estimating the goodness of fit of empirical distributions. Ann. Math. Statist. 19 (1948), 279-281.
• 13: R. R. Coveyou, Serial Correlation in the Generation of Pseudo-Random Numbers, Journal of the ACM (JACM), v.7 n.1, p.72-74, Jan. 1960 [doi>10.1145/321008.321018]
• 14: Box, G. E. P., AND MULLER, M.E. A note on the generation of random normal deviates. Ann. Math. Statist. 29 (1958), 610-613.
• 15: VON NEUMAN, J. Various techniques used in connection with random digits. In Monte Carlo Methods, Nat. Bur. Standards Appl. Math. Series, No. 12, US Gov't. Printing Off., Washington, D. C., 1951.

INDEX TERMS

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

General Terms:
Measurement, Performance, Theory