On the discrepancy of GFSR pseudorandom numbers

ABSTRACT

A new summation formula based on the orthogonal property of Walsh functions is devised. Using this formula, the k-dimensional discrepancy of the generalized feedback shift register (GFSR) pseudorandom numbers is derived. The relation between the discrepancy and k-distribution of GFSR sequences is also obtained. Finally the definition of optimal GPSR pseudorandom number generators is introduced.

REFERENCES

• 1: BEAUCHAMP, K.G. Walsh Functions and Their Applications. Academic Press, London, 1975.
• 2: BOROSH, I., AND NIEDERREITER, H. Optimal multipliers for pseudorandom number generation by the linear congruential method. BIT 23 (1983), 65-74.
• 3: 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]
• 4: KNtrrH, D. E. The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 2nd ed. Addison-Wesley, Reading, Mass., 1981.
• 5: KuNz, H. O., AND RAMM-ARNFr, J. Walsh matrices. Arch. Elektron. Ubertragungstech. (Electron. Commun.) 32 (1978), 56-58.
• 6: 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]
• 7: MARSAGLIA, G. Random number generator. In Encyclopedia of Computer Science, A. Ralston and C. L. Meek, Eds. Petrocelli/Charter, New York, 1976.
• 8: NIFDERREITER, H. Pseudorandom numbers and optimal coefficients. Adv. Math. 26 (1977), 99-181.
• 9: NIEDERREITER, H. Quasi-Monte Carlo methods and pseudorandom numbers. Bull. Amer. Math. Soc. 84 (1978), 957-1041.
• 10: NIEDFRRErrER, H. Applications des corps finis aux nombres pesudoaleatoires. Sere. Theorie des Nombres 1982-83, Exp. 38. Univ. de Bordeaux 1, Talence, France, 1983.
• 11: NIEDFRREIT~R, H. The performance of K-step pseudorandom number generators under the uniformity test. SIAM J. Sci. Statist. Comput. 5 (1984), 798-810.
• 12: TAUSWORTHE, R. C. Random numbers generated by linear recurrence modulo two. Math. Comput. 19 (1965), 201-209.
• 13: Shu Tezuka, Walsh-spectral test for GFSR pseudorandom numbers, Communications of the ACM, v.30 n.8, p.731-735, Aug. 1987 [doi>10.1145/27651.27657]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

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

General Terms:
Algorithms, Measurement, Performance, Theory, Verification