Fourier Analysis of Uniform Random Number Generators

ABSTRACT

A method of analysis of uniform random number generators is developed, applicable to almost all practical methods of generation. The method is that of Fourier analysis of the output sequences of such generators. With this tool it is possible to understand and predict relevant statistical properties of such generators and compare and evaluate such methods. Many such analyses and comparisons have been carried out. The performance of these methods as implemented on differing computers is also studied. The main practical conclusions of the study are: (a) Such a priori analysis and prediction of statistical behavior of uniform random number generators is feasible. (b) The commonly used multiplicative congruence method of generation is satisfactory with careful choice of the multiplier for computers with an adequate (≥ ∼ 35-bit) word length. (c) Further work may be necessary on generators to be used on machines of shorter word length.

REFERENCES

• 1: J. Certaine, On Sequences of Pseudo-Random Numbers of Maximal Length, Journal of the ACM (JACM), v.5 n.4, p.353-356, Oct. 1958 [doi>10.1145/320941.320949]
• 2: 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]
• 3: MOIRDELL, L.J. Observation on the minimum of a quadratic form in eight variables. J. London Math. Soc. 19 (1944), 3-6.
• 4: CASSLS, J. W: S. An Introduction to the Geometry of Numbers. Springer-Verlag, Berlin, 1959, pp. 31,332. (This contains proofs of theorems referred to in the text.)
• 5: 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]
• 6: Martin Greenberger, Method in randomness, Communications of the ACM, v.8 n.3, p.177-179, March 1965 [doi>10.1145/363791.363827]
• 7: HULL, W..E., AND DOBELL, A.R. Random number generators. SIAM Rev. 4 (1962), 229- 254. (This contains a good survey of the field and a comprehensive bibliography.)
• 8: JANSSON, B. Autocorrelations between pseudo-random numbers. NordisK Tidskr. Informations-Behandling 4 (1964), 6-27.
• 9: WEYL, H. Uber die Gleichverteilung yon Zahlen rood Eins. Math. Ann. 77 (1916); also Selecta Hermann Weyl. Birkhauser Verlag, Basel, 1956, p. 111. (This contains proofs of theorems referred to in the text.)

INDEX TERMS

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

General Terms:
Measurement, Performance, Theory