Walsh-spectral test for GFSR pseudorandom numbers

ABSTRACT

By applying Weyl's criterion for k-distributivity to GFSR sequences, we derive a new theoretical test for investigating the statistical property of GFSR sequences. This test provides a very useful measure for examining the k-distribution, that is, the statistical independence of the k-tuple of successive terms of GFSR sequences. In the latter half of this paper, we describe an efficient procedure for performing this test and furnish experimental results obtained from applying it to several GFSR generators with prime period lengths.

REFERENCES

• 1: Beauchamp. K.C. Walsh Functions and Their Applications. Academic Press. New York. 1975.
• 2: 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]
• 3: Franklin. J.N. Deterministic simulalion of random processes. Math. Compuf. 17.81 (1963). 28-59.
• 4: Fushimi. M., and Tezuka. S. Pseudorandom number generators based on maximum length linearly recurring sequences. J. Fac. Eng. A-17 (1979). 42-43 (in Japanese).
• 5: M. Fushimi , S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Communications of the ACM, v.26 n.7, p.516-523, July 1983 [doi>10.1145/358150.358159]
• 6: Kirkpatrik. S.. and Sloll. E.P. A very fast shift register sequence random number generator. J. Compur. Phys. 40. 2 (1981). 517-526.
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: 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.
• 9: T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
• 10: Marsaglia. G. Random number generator. In Encyclopedia of Computer Science. A. Ralston and C.L. Meek. Eds. Petrocelli/Charter. New York. 1976.
• 11: Tausworthe. R.C. Random numbers generated by linear recurrence module two. Math. Cornput. 19. 90 (1965). 201-209.
• 12: Tezuka. S. The asymptotic randomness of GFSR pseudorandom numbers. Trans. Inf. Process. Soc. Japan 25. 4 (July 1984). 681-684 (in Japanese).
• 13: Tezuka. S. The theoretical comparison between cogruential methods and GFSR algorithms. jSI Res. Rep. TR87-0001. IBM japan. Tokyo. 1984.
• 14: 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]
• 15: 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]
• 16: Walsh. J.L. A closed set of orthogonal functions. Am. 1. Math. 45 (1923). 5-24.
• 17: Weyl. H. Uber die gleichverteilung van zahlen mod. eins. Math. Ann.
• 18: 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]

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Experimentation, Measurement, Theory