More Web Proxy on the site http://driver.im/

article

Free access

Walsh-spectral test for GFSR pseudorandom numbers

Author:

Shu TezukaAuthors Info & Claims

Communications of the ACM, Volume 30, Issue 8

Pages 731 - 735

https://doi.org/10.1145/27651.27657

Published: 01 August 1987 Publication History

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]

Coveyou. R.R. and MacPherson. R.D. Fourier analysis of uniform random number generators. J. ACM 14. 1 (Jan. 1967). 100-119.

Digital Library

[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]

Fushimi. M. and Tezuka. S. The K-distribution of generalized feedback shift rcgisler pseudorandom numbers. Commun. ACM 26. 7 (July 1983). 516-523.

Digital 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.

[7]

Knuth. D.E. The Art of Computer Programming. Vol. 2. Seminumerical Algorithms. 2nd ed. Addison-Wesley, Reading, Mass., 1981.

Digital 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.

Digital Library

[9]

Lewis. T.G. and Payne, W.H. Generalized feedback shift register pseudorandom number algorithm. J. ACM 20. 3 (July 1973). 456-466.

Digital Library

[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]

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.

Digital 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.

Digital Library

[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]

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.

Digital Library

Cited By

Sherif YDear R(2016)Using Walsh Functions to Test a New Composite Sherif-Dear (CSD) Random Number GeneratorSIMULATION10.1177/00375497950650050665:5(338-342)Online publication date: 19-Aug-2016
https://doi.org/10.1177/003754979506500506
Dick J(2014) Discrepancy bounds for infinite-dimensional order two digital sequences over Journal of Number Theory10.1016/j.jnt.2013.09.012136(204-232)Online publication date: Mar-2014
https://doi.org/10.1016/j.jnt.2013.09.012
Hellekalek P(2011)On correlation analysis of pseudorandom numbersMonte Carlo and Quasi-Monte Carlo Methods 199610.1007/978-1-4612-1690-2_16(251-265)Online publication date: 23-May-2011
https://doi.org/10.1007/978-1-4612-1690-2_16
Show More Cited By

Index Terms

Walsh-spectral test for GFSR pseudorandom numbers
1. Applied computing
  1. Physical sciences and engineering
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
  2. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Random number generation

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 30, Issue 8

Aug. 1987

79 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/27651

Editor:
Peter J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

Copyright © 1987 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1987

Published in CACM Volume 30, Issue 8

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
490
Total Downloads

Downloads (Last 12 months)96
Downloads (Last 6 weeks)10

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sherif YDear R(2016)Using Walsh Functions to Test a New Composite Sherif-Dear (CSD) Random Number GeneratorSIMULATION10.1177/00375497950650050665:5(338-342)Online publication date: 19-Aug-2016
https://doi.org/10.1177/003754979506500506
Dick J(2014) Discrepancy bounds for infinite-dimensional order two digital sequences over Journal of Number Theory10.1016/j.jnt.2013.09.012136(204-232)Online publication date: Mar-2014
https://doi.org/10.1016/j.jnt.2013.09.012
Hellekalek P(2011)On correlation analysis of pseudorandom numbersMonte Carlo and Quasi-Monte Carlo Methods 199610.1007/978-1-4612-1690-2_16(251-265)Online publication date: 23-May-2011
https://doi.org/10.1007/978-1-4612-1690-2_16
L’Ecuyer PLemieux C(2005)Recent Advances in Randomized Quasi-Monte Carlo MethodsModeling Uncertainty10.1007/0-306-48102-2_20(419-474)Online publication date: 2005
https://doi.org/10.1007/0-306-48102-2_20
Hellekalek P(1998)On the Assessment of Random and Quasi-Random Point SetsRandom and Quasi-Random Point Sets10.1007/978-1-4612-1702-2_2(49-108)Online publication date: 1998
https://doi.org/10.1007/978-1-4612-1702-2_2
Imperiale C(1997)Programmable uniform-Gaussian, quasi-white noise generator and data acquisition-processing system for electrophysiologyMeasurement10.1016/S0263-2241(97)00023-720:3(149-163)Online publication date: Mar-1997
https://doi.org/10.1016/S0263-2241(97)00023-7
Sherif YDear R(1995)An efficient algorithm for testing the quality of the output of random number generatorsAdvances in Engineering Software10.1016/0965-9978(95)00013-M22:2(69-77)Online publication date: Jan-1995
https://doi.org/10.1016/0965-9978(95)00013-M
Vattulainen IKankaala KSaarinen JAla-Nissila T(1995)A comparative study of some pseudorandom number generatorsComputer Physics Communications10.1016/0010-4655(95)00015-886:3(209-226)Online publication date: May-1995
https://doi.org/10.1016/0010-4655(95)00015-8
Hellekalek P(1995)General discrepancy estimates III: The Erd�s-Tur�n-Koksma inequality for the Haar function systemMonatshefte f�r Mathematik10.1007/BF01470062120:1(25-45)Online publication date: Mar-1995
https://doi.org/10.1007/BF01470062
Niederreiter H(1995)New Developments in Uniform Pseudorandom Number and Vector GenerationMonte Carlo and Quasi-Monte Carlo Methods in Scientific Computing10.1007/978-1-4612-2552-2_5(87-120)Online publication date: 1995
https://doi.org/10.1007/978-1-4612-2552-2_5
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents