Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T14:16:46.333Z Has data issue: false hasContentIssue false
  • English
  • Français

An Expanded Set of Correlation Tests for Linear Congruential Random Number Generators*

Published online by Cambridge University Press:  12 September 2008

Ora Engelberg Percus  and
Jerome K. Percus
Ora Engelberg Percus
Affiliation:
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012
Jerome K. Percus
Affiliation:
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012
Get access Rights & Permissions [Opens in a new window]

Abstract

An analytic study is made of the correlation structure of Tausworthe and linear congruential random number generators. The former case is analyzed by the bit mask correlations recently introduced by Compagner. The latter is studied first by an extension to word masks, which include spectral test coefficients as special cases, and then by the bit mask procedure. Although low order bit mask coefficients vanish in both cases, the Tausworthe generator appears to produce a substantially smaller non-vanishing correlation set for large masks – but with larger correlation values – than does the linear congruential.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 2 , June 1992 , pp. 161 - 168
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Compagner, A. (1991) J. Stat. Phys. 63, 883.CrossRefGoogle Scholar
[2]Coveyou, R. R. and MacPherson, R. D. (1967) J. Assoc. Comp. Much. 14, 100.CrossRefGoogle Scholar
[3]Hull, T. E. and Dobell, A. R. (1962) SIAM Rev. 4, 230.CrossRefGoogle Scholar
[4]Kalos, M. H. and Whitlock, P. A. (1986) Monte Carlo Methods. Wiley-Interscience.CrossRefGoogle Scholar
[5]Kirkpatrick, S. and Stoll, E. P. (1981) J. Comp. Phys. 40, 517.CrossRefGoogle Scholar
[6]Knuth, D. E. (1981) The Art of Computer Programming, Vol. II. Addison-Wesley.Google Scholar
[7]Lehmer, D. H. (1949) Proc. 2nd Sympos. on Large-scale Digital Calculating Machinery. Cambridge, Mass.Google Scholar
[8]Marsaglia, G. and Zaman, A. (1991) Ann. Appl. Prob. 1, 462.CrossRefGoogle Scholar
[9]See also Niederreiter, H. (1978) Bull. Am. Math. Soc. 84, 957.CrossRefGoogle Scholar
[10]Percus, O. E. and Percus, J. K. (1988) J. Comp. Phys. 77, 267.CrossRefGoogle Scholar
[11]Tausworthe, R. C. (1965) Math. Comp. 19, 201.CrossRefGoogle Scholar