Autocorrelation Peaks in Congruential Pseudorandom Number Generators
- 1 May 1976
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-25 (5) , 457-460
- https://doi.org/10.1109/tc.1976.1674632
Abstract
One of the desirable properties of a pseudorandom number generator is that the sequence of numbers it generates should have very low autocorrelation for all shifts except for zero shift and those that are multiples of its cycle length. Due to the simple methods of constructing random numbers via modulo arithmetic, the ideal is often not quite fulfilled. The results of this paper were obtained by the simple method of examining the complete correlation structure of several generators of the same type and small cycle length. Once the regularities were discovered, the mathematical relationships were derived which describe the regular behavior for all generators of the same class. As examples, it is shown in this paper that high correlation exists in mixed and multiplicative congruential random number generators and prime moduli Lehmer generators for shifts a fraction of their cycle lengths.Keywords
This publication has 6 references indexed in Scilit:
- The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number GeneratorsJournal of the ACM, 1971
- Random-number generation on digital computersIEEE Spectrum, 1967
- Random, Pseudorandom, and Quasirandom NumbersPublished by Springer Nature ,1964
- Notes on a New Pseudo-Random Number GeneratorJournal of the ACM, 1961
- A New Pseudo-Random Number GeneratorJournal of the ACM, 1960
- Serial Correlation in the Generation of Pseudo-Random NumbersJournal of the ACM, 1960