Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Statistical independence of a new class of inversive congruential pseudorandom numbers


Author: Jürgen Eichenauer-Herrmann
Journal: Math. Comp. 60 (1993), 375-384
MSC: Primary 65C10; Secondary 11K45
DOI: https://doi.org/10.1090/S0025-5718-1993-1159168-9
MathSciNet review: 1159168
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Linear congruential pseudorandom numbers show several undesirable regularities which can render them useless for certain stochastic simulations. This was the motivation for important recent developments in nonlinear congruential methods for generating uniform pseudorandom numbers. It is particularly promising to achieve nonlinearity by employing the operation of multiplicative inversion with respect to a prime modulus. In the present paper a new class of such inversive congruential generators is introduced and analyzed. It is shown that they have excellent statistical independence properties and model true random numbers very closely. The methods of proof rely heavily on Weil-Stepanov bounds for rational exponential sums.


References [Enhancements On Off] (What's this?)

  • [1] I. Borosh and H. Niederreiter, Optimal multipliers for pseudo-random number generation by the linear congruential method, BIT 23 (1983), 65-74. MR 689604 (84e:65012)
  • [2] J. Eichenauer, H. Grothe, and J. Lehn, Marsaglia's lattice test and non-linear congruential pseudo random number generators, Metrika 35 (1988), 241-250.
  • [3] J. Eichenauer, H. Grothe, J. Lehn, and A. Topuzoglu, A multiple recursive non-linear congruential pseudo random number generator, Manuscripta Math. 59 (1987), 331-346. MR 909849 (89f:65008)
  • [4] J. Eichenauer and J. Lehn, A non-linear congruential pseudorandom number generator, Statist. Papers 27 (1986), 315-326. MR 877295 (88i:65014)
  • [5] -, On the structure of quadratic congruential sequences, Manuscripta Math. 58 (1987), 129-140. MR 884989 (88h:65019)
  • [6] J. Eichenauer, J. Lehn, and A. Topuzoglu, A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp. 51 (1988), 757-759. MR 958641 (89i:65007)
  • [7] J. Eichenauer and H. Niederreiter, On Marsaglia's lattice test for pseudorandom numbers, Manuscripta Math. 62 (1988), 245-248. MR 963009 (90c:65011)
  • [8] J. Eichenauer-Herrmann, A remark on the discrepancy of quadratic congruential pseudorandom numbers, J. Comput. Appl. Math. (to appear) MR 1193815 (93i:65010)
  • [9] -, Construction of inversive congruential pseudorandom number generators with maximal period length, J. Comput. Appl. Math. 40 (1992), 345-349. MR 1170913 (93d:65010)
  • [10] -, Inversive congruential pseudorandom numbers: a tutorial, Internat. Statist. Rev. 60 (1992), 167-176.
  • [11] -, Inversive congruential pseudorandom numbers avoid the planes, Math. Comp. 56 (1991), 297-301. MR 1052092 (91k:65021)
  • [12] -, On the autocorrelation structure of inversive congruential pseudorandom number sequences, Statist. Papers (to appear) MR 1186171 (94b:65016)
  • [13] -, On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus, Manuscripta Math. 71 (1991), 153-161. MR 1101266 (92c:11081)
  • [14] J. Eichenauer-Herrmann and H. Grothe, A new inversive congruential pseudorandom number generator with power of two modulus, ACM Trans. Modeling Computer Simulation (to appear)
  • [15] J. Eichenauer-Herrmann, H. Grothe, H. Niederreiter, and A. Topuzoglu, On the lattice structure of a nonlinear generator with modulus $ {2^\alpha }$, J. Comput. Appl. Math. 31 (1990), 81-85. MR 1068151 (91j:65012)
  • [16] J. Eichenauer-Herrmann and H. Niederreiter, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus, Math. Comp. 58 (1992), 775-779. MR 1122066 (92i:65018)
  • [17] -, On the discrepancy of quadratic congruential pseudorandom numbers, J. Comput. Appl. Math. 34 (1991), 243-249. MR 1107870 (92c:65010)
  • [18] J. Eichenauer-Herrmann and A. Topuzoglu, On the period length of congruential pseudorandom number sequences generated by inversions, J. Comput. Appl. Math. 31 (1990), 87-96. MR 1068152 (92e:65008)
  • [19] G. S. Fishman, Multiplicative congruential random number generators with modulus $ {2^\beta }$: An exhaustive analysis for $ \beta = 32$ and a partial analysis for $ \beta = 48$, Math. Comp. 54 (1990), 331-344. MR 993929 (91e:65012)
  • [20] G. S. Fishman and L. R. Moore, An exhaustive analysis of multiplicative congruential random number generators with modulus $ {2^{31}} - 1$, SIAM J. Sci. Statist. Comput. 7 (1986), 24-45; Erratum, ibid., p. 1058. MR 819455 (87g:65010a)
  • [21] F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), 329-344. MR 1076267 (91i:65013)
  • [22] J. Kiefer, On large deviations of the empiric d.f. of vector chance variables and a law of the iterated logarithm, Pacific J. Math. 11 (1961), 649-660. MR 0131885 (24:A1732)
  • [23] D. E. Knuth, The art of computer programming, vol. 2, 2nd ed., Addison-Wesley, Reading, MA, 1981. MR 633878 (83i:68003)
  • [24] R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, MA, 1983. MR 746963 (86c:11106)
  • [25] G. Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25-28. MR 0235695 (38:3998)
  • [26] -, Regularities in congruential random number generators, Numer. Math. 16 (1970), 8-10. MR 0273775 (42:8651)
  • [27] H. Niederreiter, Pseudo-random numbers and optimal coefficients, Adv. in Math. 26 (1977), 99-181. MR 0476679 (57:16238)
  • [28] -, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 957-1041. MR 508447 (80d:65016)
  • [29] -, The serial test for pseudo-random numbers generated by the linear congruential method, Numer. Math. 46 (1985), 51-68. MR 777824 (86i:65010)
  • [30] -, Remarks on nonlinear congruential pseudorandom numbers, Metrika 35 (1988), 321-328. MR 980847 (90e:11119)
  • [31] -, Statistical independence of nonlinear congruential pseudorandom numbers, Monatsh. Math. 106 (1988), 149-159. MR 968332 (89j:11079)
  • [32] -, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), 135-144. MR 971407 (90e:65008)
  • [33] -, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers, Math. Comp. 55 (1990), 277-287. MR 1023766 (91e:65016)
  • [34] -, Recent trends in random number and random vector generation, Ann. Oper. Res. 31 (1991), 323-346. MR 1118905 (92h:65010)
  • [35] -, Nonlinear methods for pseudorandom number and vector generation, Simulation and Optimization (G. Pflug and U. Dieter, eds.), Lecture Notes in Economics and Math. Systems, vol. 374, Springer, Berlin, 1992, pp. 145-153.
  • [36] B. D. Ripley, Computer generation of random variables: a tutorial, Internat. Statist. Rev. 51 (1983), 301-319. MR 731146 (85a:65016)
  • [37] -, The lattice structure of pseudo-random number generators, Proc. Roy. Soc. London Ser. A 389 (1983), 197-204. MR 719645 (85i:65010)
  • [38] S. A. Stepanov, On estimating rational trigonometric sums with prime denominator, Trudy Mat. Inst. Steklov. 112 (1971), 346-371. (Russian) MR 0318158 (47:6706)
  • [39] A. Weil, On some exponential sums, Proc. Nat. Acad. Sci. U.S.A. 34 (1948), 204-207. MR 0027006 (10:234e)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10, 11K45

Retrieve articles in all journals with MSC: 65C10, 11K45


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1159168-9
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society