A comparative analysis of two concepts in the generation of uniform pseudo-random numbers

ABSTRACT

In recent years, considerable attention has been given to find reliable methods capable of producing, within a digital computer, pseudo-random numbers obeying the uniform distribution on the unit interval. Apparently, the most popular method has been the congruence algorithm whose basic form Xi+1 &equil; aX1 + b mod 2m (1) can be easily implemented on a binary computer with word size of m bits. Since its introduction, a number of papers1-3 have been written in which techniques, such as suggesting formulae1 to compute optimal values for a and b, have been presented to improve the statistical properties of the method. As a consequence, several versions with values for a and b to suit everybody's needs are now in existence. One must be aware that an analysis based on statistical testing cannot be entirely conclusive, especially if the power of some tests used is not known. Nevertheless, the comparative analysis of this study does indicate that a generator based on Tausworthe's concept exhibits a statistical behavior that is as good if not superior to that of the congruence algorithm. Therefore, the following advantage in its use are apparent: (1) Its functional form and statistical behavior are entirely machine independent. (2) It has been shown analytically that it generates values of a random variable uniformly distributed on the unit interval. (3) It can be easily programmed in FORTRAN without sacrificing any of its characteristics. (To the author's knowledge, none of these advantages can be claimed by any of the existing congruence algorithms.)

REFERENCES

• 1: 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]
• 2: Martin Greenberger, Notes on a New Pseudo-Random Number Generator, Journal of the ACM (JACM), v.8 n.2, p.163-167, April 1961 [doi>10.1145/321062.321065]
• 3: 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]
• 4: R C TAUSWORTHE Random numbers generated by linear recurrence modulo two Mathematics of Computation 19 pp 201-209 1965
• 5: S W GOLOMB Sequences with randomness properties Martin Co Baltimore Md 1955
• 6: N ZIERLER Linear recurring sequences J Soc Indust Appl Math vol 7 pp 31-48 1959
• 7: E J WATSON Primitive polynomials mod 2 Mathematics of Computation vol 16 pp 368-369 1962
• 8: G C CANAVOS Statistical study of a uniform and a normal random number generator Master of Science Thesis Virginia Polytechnic Institute Blacksburg Va 1966
• 9: P G HOEL Introduction to mathematical statistics John Wiley and Sons Inc New York 1965 3rd ed pp 335-341
• 10: M G KENDALL and A STUART The advanced theory of statistics Hafner Publishing Co New York 1961 Vol II p 463
• 11: A M MOOD and G A GRAYBILL Introduction to the theory of statistics McGraw-Hill Book Company Inc New York 1963 pp. 409-412
• 12: S GORENSTEIN Random number generation for the general purpose systems simulator Technical Report 17-161 IBM Advanced Systems Development Division Yorktown Heights N Y 1966
• 13: A WALD and J WOLFOWITZ An exact test for randomness in the non-parametric case based on serial correlation Annals of Mathematical Statistics vol 14 pp 378-388 1943
• 14: H B MANN and A WALD On the choice of the number of intervals in the application of the chi-square test Annals of Mathematical Statistics vol 13 pp 306-317 1942
• 15: F J MASSEY JR A note on the power of a non-parametric test Annals of Mathematical Statistics vol 21 pp 440-443 1950

INDEX TERMS

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

General Terms:
Theory