Distribution properties of multiply-with-carry random number generators. (English) Zbl 0866.65003
Summary: We study the multiply-with-carry family of generators proposed by G. Marsaglia as a generalization of previous add-with-carry families. We define for them an 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. Our results are stated in a general context and are applied to a related complementary multiply-with-carry family of generators.
MSC:
| 65C10 | Random number generation in numerical analysis |
References:
| [1] | Raymond Couture and Pierre L’Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. 62 (1994), no. 206, 799 – 808. · Zbl 0803.65005 |
| [2] | Erich Hecke, Lectures on the theory of algebraic numbers, Graduate Texts in Mathematics, vol. 77, Springer-Verlag, New York-Berlin, 1981. Translated from the German by George U. Brauer, Jay R. Goldman and R. Kotzen. · Zbl 0504.12001 |
| [3] | Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002 |
| [4] | Pierre L’Ecuyer, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77 – 120. Simulation and modeling. · Zbl 0843.65004 · doi:10.1007/BF02136827 |
| [5] | P. L’Ecuyer and R. Couture, An implementation of the lattice and spectral tests for multiple recursive linear random number generators, Informes Journal on Computing, to appear, 1997. · Zbl 0889.65004 |
| [6] | G. Marsaglia, Yet another rng, Posted to the electronic billboard sci.stat.math, August 1, 1994. |
| [7] | George Marsaglia and Arif Zaman, A new class of random number generators, Ann. Appl. Probab. 1 (1991), no. 3, 462 – 480. · Zbl 0733.65005 |
| [8] | Władysław Narkiewicz, Elementary and analytic theory of algebraic numbers, PWN — Polish Scientific Publishers, Warsaw, 1974. Monografie Matematyczne, Tom 57. · Zbl 0276.12002 |
| [9] | Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. · Zbl 0761.65002 |
| [10] | C. L. Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arithmetica 1 (1935), 83-86. · JFM 61.0170.02 |
| [11] | S. Tezuka, P. L’Ecuyer, and R. Couture, On the add-with-carry and subtract-with-borrow random number generators, ACM Transactions of Modeling and Computer Simulation 3 (1994), no. 4, 315-331. · Zbl 0843.65003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
