Article

Free access

Linear recurrences with carry as uniform random number generators

Authors:

Raymond Couture,

Pierre L'EcuyerAuthors Info & Claims

WSC '95: Proceedings of the 27th conference on Winter simulation

Pages 263 - 267

https://doi.org/10.1145/224401.224613

Published: 01 December 1995 Publication History

PDF eReader

Abstract

We study the multiply-with-carry family of generators proposed by G. Marsaglia (1994) as a generalisation of the previous add-with-carry and subtract-with-borrow families of G. Marsaglia and A. Zaman (1991). We define for them a general (infinite) state space and focus our attention on the (finite) subset of recurrent states. This subset will, in turn, split into possibly several subgenerators. We discuss the uniformity of the d-dimensional distribution of the output of these subgenerators over their full period. In order to improve this uniformity for higher dimensions, we propose a method for finding good parameters in terms of the spectral test.

References

[1]

Couture, R., and P. L'Ecuyer. 1994. On the lattice structure of certain linear congruential sequences related to AWC/SWB generators. Mathematics of Computation, 62(206) :798-808.

Digital Library

Google Scholar

[2]

Knuth, D. E. 1981. The Art of Computer Programming, Volume 2: Semznumerical Algorithms. second ed., volume 2. Addison-Wesley.

Digital Library

Google Scholar

[3]

L'Ecuyer, P. 1994. Uniform random number generation. Annals of Operations Research, 53:77-120.

Crossref

Google Scholar

[4]

Marsaglia, G. 1994. Yet another rng. Posted to the electronic billboard sci. star .ma, August 1.

Google Scholar

[5]

Marsaglia, G., and A. Zaman. 1991. A new class of random number generators. The Annals of Applied Probability, 1:462-480.

Crossref

Google Scholar

[6]

Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. volume 63 of SIAM CBMS-NSF Regional Conference Series in Applied Mathematics. Philadelphia: SIAM.

Digital Library

Google Scholar

[7]

Tezuka, S., P. L'Ecuyer., and R. Couture. 1994. On the add-with-carry and subtract-with-borrow randora number generators. A CM Transactions of Modeling and Computer Simulation, 3(4):315-331.

Digital Library

Google Scholar

Cited By

View all

de Oliveira TMarranghello N(2011)Design of a reconfigurable pseudorandom number generator for use in intelligent systemsNeurocomputing10.1016/j.neucom.2010.12.02174:10(1510-1519)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.neucom.2010.12.021
L'Ecuyer P(1998)Uniform random number generatorsProceedings of the 30th conference on Winter simulation10.5555/293172.293213(97-104)Online publication date: 1-Dec-1998
https://dl.acm.org/doi/10.5555/293172.293213
L'Ecuyer P(1997)Uniform random number generatorsProceedings of the 29th conference on Winter simulation10.1145/268437.268461(127-134)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1145/268437.268461

Index Terms

Linear recurrences with carry as uniform random number generators
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
  2. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Random number generation

Recommendations

Bit-Wise Behavior of Random Number Generators

In 1985, G. Marsaglia proposed the m-tuple test, a runs test on bits, as a test of nonrandomness of a sequence of pseudorandom integers. We try this test on the outputs from a large set of pseudorandom number generators and discuss the behavior of the ...
Resolution-stationary random number generators

Besides speed and period length, the quality of uniform random number generators (RNGs) is usually assessed by measuring the uniformity of their point sets, formed by taking vectors of successive output values over their entire period length. For F"2-...
Testing parallel random number generators

Monte Carlo computations are considered easy to parallelize. However, the results can be adversely affected by defects in the parallel pseudorandom number generator used. A parallel pseudorandom number generator must be tested for two types of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WSC '95: Proceedings of the 27th conference on Winter simulation

December 1995

1493 pages

ISBN:0780330188

Chairmen:
William R. Lilegdon
Pritsker Corp., West Lafayette, IN
,
David Goldsman
Georgia Institute of Technology, Atlanta
,
Editors:
Christos Alexopoulos
Georgia Institute of Technology, Atlanta
,
Keebom Kang
Naval Postgraduate School, Monterey, CA

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

WSC95

Sponsor:

IIE
IEEE-SMCS
INFORMS/CS
ASA
ACM
SCS
SIGSIM
IEEE-CS
NIST

WSC95: 1995 Winter Simulation Conference

December 3 - 6, 1995

Virginia, Arlington, USA

Acceptance Rates

WSC '95 Paper Acceptance Rate 122 of 183 submissions, 67%;

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
222
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)4

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

de Oliveira TMarranghello N(2011)Design of a reconfigurable pseudorandom number generator for use in intelligent systemsNeurocomputing10.1016/j.neucom.2010.12.02174:10(1510-1519)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.neucom.2010.12.021
L'Ecuyer P(1998)Uniform random number generatorsProceedings of the 30th conference on Winter simulation10.5555/293172.293213(97-104)Online publication date: 1-Dec-1998
https://dl.acm.org/doi/10.5555/293172.293213
L'Ecuyer P(1997)Uniform random number generatorsProceedings of the 29th conference on Winter simulation10.1145/268437.268461(127-134)Online publication date: 1-Dec-1997
https://dl.acm.org/doi/10.1145/268437.268461

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Bit-Wise Behavior of Random Number Generators

Resolution-stationary random number generators

Testing parallel random number generators