Shu Tezuka
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.
- 1 Beauchamp. K.C. Walsh Functions and Their Applications. Academic Press. New York. 1975.Google Scholar
- 2 Coveyou. R.R. and MacPherson. R.D. Fourier analysis of uniform random number generators. J. ACM 14. 1 (Jan. 1967). 100-119. Google ScholarDigital Library
- 3 Franklin. J.N. Deterministic simulalion of random processes. Math. Compuf. 17.81 (1963). 28-59.Google ScholarCross Ref
- 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).Google Scholar
- 5 Fushimi. M. and Tezuka. S. The K-distribution of generalized feedback shift rcgisler pseudorandom numbers. Commun. ACM 26. 7 (July 1983). 516-523. Google ScholarDigital Library
- 6 Kirkpatrik. S. and Sloll. E.P. A very fast shift register sequence random number generator. J. Compur. Phys. 40. 2 (1981). 517-526.Google Scholar
- 7 Knuth. D.E. The Art of Computer Programming. Vol. 2. Seminumerical Algorithms. 2nd ed. Addison-Wesley, Reading, Mass., 1981. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 9 Lewis. T.G. and Payne, W.H. Generalized feedback shift register pseudorandom number algorithm. J. ACM 20. 3 (July 1973). 456-466. Google ScholarDigital Library
- 10 Marsaglia. G. Random number generator. In Encyclopedia of Computer Science. A. Ralston and C.L. Meek. Eds. Petrocelli/Charter. New York. 1976.Google Scholar
- 11 Tausworthe. R.C. Random numbers generated by linear recurrence module two. Math. Cornput. 19. 90 (1965). 201-209.Google Scholar
- 12 Tezuka. S. The asymptotic randomness of GFSR pseudorandom numbers. Trans. Inf. Process. Soc. Japan 25. 4 (July 1984). 681-684 (in Japanese).Google Scholar
- 13 Tezuka. S. The theoretical comparison between cogruential methods and GFSR algorithms. jSI Res. Rep. TR87-0001. IBM japan. Tokyo. 1984.Google Scholar
- 14 Toolill. J.P.R. Robinson, W.D. and Adams. A.G. The runs up-anddown performance of Tausworthe pseudo-random number generators. J. ACM 18. 3 (July 1971). 381-399. Google ScholarDigital Library
- 15 Tootill. J.P.R. Robinson. W.D. and Eagle, D.J. A" asymptotically random Tausworthe sequence. I. ACM 20. 3 (July 1973). 469-481. Google ScholarDigital Library
- 16 Walsh. J.L. A closed set of orthogonal functions. Am. 1. Math. 45 (1923). 5-24.Google Scholar
- 17 Weyl. H. Uber die gleichverteilung van zahlen mod. eins. Math. Ann.Google Scholar
- 18 Whittlesey. J.R.B. A comparison of the correlational behavior of random number generators for the IBM 360. Cwvnrun. ACM II. 9 (Sept. 1968). 641-644. Google ScholarDigital Library
Index Terms
- Walsh-spectral test for GFSR pseudorandom numbers
Recommendations
Digital inversive pseudorandom numbers
A new algorithm, the digital inversive method, for generating uniform pseudorandom numbers is introduced. This algorithm starts from an inversive recursion in a large finite field and derives pseudorandom numbers from it by the digital method. If the ...
On the statistical independence of nonlinear congruential pseudorandom numbers
Recently, several nonlinear congruential methods for generating uniform pseudorandom numbers have been proposed and analysed. In the present note, further statistical independence properties of a general class of nonlinear congruential pseudorandom ...
Test Length for Pseudorandom Testing
The process of determining the required test length for a desired level of confidence for pseudorandom testing using a random sampling without replacement model is examined. The differences between random and pseudorandom testing are discussed and ...
Reviews
John B. Slater
In the study of algorithms for pseudorandom numbers, an important factor is the usability of a sequence of pseudorandom numbers for particular purposes. Their use in a periodic fashion is frequent, and so the statistical independence of k-tuples of successive terms for particular ks is an important factor in choosing such an algorithm. (The periodicity of the sequence implies the existence of some ks, albeit hopefully rather large, for which independence does not hold.) The paper uses Weyl's necessary and sufficient condition for k:-distributivity, defined in terms of Walsh functions. It applies a discrete version of the formula to GFSR sequences, that is, those derived by the successive multiplication of the vector of the binary digits of the preceding number by a non-singular matrix over GF(2). This leads to an explicit criterion for a regular k-distribution that is easy to compute. The criterion is applied to a number of specific generators, and there is some further discussion of other uses of the test. The paper is easy to read, and the result will interest those intending to use pseudorandom number generators to produce numbers to be used in regular fashions in their work.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments