Statistical independence of a new class of inversive congruential pseudorandom numbers
HTML articles powered by AMS MathViewer
- by Jürgen Eichenauer-Herrmann PDF
- Math. Comp. 60 (1993), 375-384 Request permission
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
- Itshak Borosh and Harald Niederreiter, Optimal multipliers for pseudorandom number generation by the linear congruential method, BIT 23 (1983), no. 1, 65–74. MR 689604, DOI 10.1007/BF01937326 J. Eichenauer, H. Grothe, and J. Lehn, Marsaglia’s lattice test and non-linear congruential pseudo random number generators, Metrika 35 (1988), 241-250.
- Jürgen Eichenauer, Holger Grothe, Jürgen Lehn, and Alev Topuzoğlu, A multiple recursive nonlinear congruential pseudo random number generator, Manuscripta Math. 59 (1987), no. 3, 331–346. MR 909849, DOI 10.1007/BF01174798
- Jürgen Eichenauer and Jürgen Lehn, A nonlinear congruential pseudorandom number generator, Statist. Hefte 27 (1986), no. 4, 315–326. MR 877295
- Jürgen Eichenauer and Jürgen Lehn, On the structure of quadratic congruential sequences, Manuscripta Math. 58 (1987), no. 1-2, 129–140. MR 884989, DOI 10.1007/BF01169087
- Jürgen Eichenauer, Jürgen Lehn, and Alev Topuzoğlu, A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp. 51 (1988), no. 184, 757–759. MR 958641, DOI 10.1090/S0025-5718-1988-0958641-1
- Jürgen Eichenauer and Harald Niederreiter, On Marsaglia’s lattice test for pseudorandom numbers, Manuscripta Math. 62 (1988), no. 2, 245–248. MR 963009, DOI 10.1007/BF01278982
- Jürgen Eichenauer-Herrmann, A remark on the discrepancy of quadratic congruential pseudorandom numbers, J. Comput. Appl. Math. 43 (1992), no. 3, 383–387. MR 1193815, DOI 10.1016/0377-0427(92)90023-Q
- Jürgen Eichenauer-Herrmann, Construction of inversive congruential pseudorandom number generators with maximal period length, J. Comput. Appl. Math. 40 (1992), no. 3, 345–349. MR 1170913, DOI 10.1016/0377-0427(92)90190-9 —, Inversive congruential pseudorandom numbers: a tutorial, Internat. Statist. Rev. 60 (1992), 167-176.
- Jürgen Eichenauer-Herrmann, Inversive congruential pseudorandom numbers avoid the planes, Math. Comp. 56 (1991), no. 193, 297–301. MR 1052092, DOI 10.1090/S0025-5718-1991-1052092-X
- J. Eichenauer-Herrmann, On the autocorrelation structure of inversive congruential pseudorandom number sequences, Statist. Papers 33 (1992), no. 3, 261–268. MR 1186171, DOI 10.1007/BF02925329
- Jürgen Eichenauer-Herrmann, On the discrepancy of inversive congruential pseudorandom numbers with prime power modulus, Manuscripta Math. 71 (1991), no. 2, 153–161. MR 1101266, DOI 10.1007/BF02568399 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)
- J. Eichenauer-Herrmann, H. Grothe, H. Niederreiter, and A. Topuzoğlu, On the lattice structure of a nonlinear generator with modulus $2^\alpha$, J. Comput. Appl. Math. 31 (1990), no. 1, 81–85. Random numbers and simulation (Lambrecht, 1988). MR 1068151, DOI 10.1016/0377-0427(90)90338-Z
- Jürgen Eichenauer-Herrmann and Harald Niederreiter, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus, Math. Comp. 58 (1992), no. 198, 775–779. MR 1122066, DOI 10.1090/S0025-5718-1992-1122066-X
- Jürgen Eichenauer-Herrmann and Harald Niederreiter, On the discrepancy of quadratic congruential pseudorandom numbers, J. Comput. Appl. Math. 34 (1991), no. 2, 243–249. MR 1107870, DOI 10.1016/0377-0427(91)90046-M
- J. Eichenauer-Herrmann and A. Topuzoğlu, On the period length of congruential pseudorandom number sequences generated by inversions, J. Comput. Appl. Math. 31 (1990), no. 1, 87–96. Random numbers and simulation (Lambrecht, 1988). MR 1068152, DOI 10.1016/0377-0427(90)90339-2
- George 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), no. 189, 331–344. MR 993929, DOI 10.1090/S0025-5718-1990-0993929-9
- George S. Fishman and Louis R. Moore III, An exhaustive analysis of multiplicative congruential random number generators with modulus $2^{31}-1$, SIAM J. Sci. Statist. Comput. 7 (1986), no. 1, 24–45. MR 819455, DOI 10.1137/0907002
- F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), no. 3, 329–344. MR 1076267, DOI 10.1016/0010-4655(90)90032-V
- 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 131885
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- George Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25–28. MR 235695, DOI 10.1073/pnas.61.1.25
- George Marsaglia, Regularities in congruential random number generators, Numer. Math. 16 (1970/71), 8–10. MR 273775, DOI 10.1007/BF02162401
- Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 476679, DOI 10.1016/0001-8708(77)90028-7
- Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S0002-9904-1978-14532-7
- Harald Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46 (1985), no. 1, 51–68. MR 777824, DOI 10.1007/BF01400255
- H. Niederreiter, Remarks on nonlinear congruential pseudorandom numbers, Metrika 35 (1988), no. 6, 321–328. MR 980847, DOI 10.1007/BF02613320
- Harald Niederreiter, Statistical independence of nonlinear congruential pseudorandom numbers, Monatsh. Math. 106 (1988), no. 2, 149–159. MR 968332, DOI 10.1007/BF01298835
- Harald Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), no. 185, 135–144. MR 971407, DOI 10.1090/S0025-5718-1989-0971407-2
- Harald Niederreiter, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers, Math. Comp. 55 (1990), no. 191, 277–287. MR 1023766, DOI 10.1090/S0025-5718-1990-1023766-0
- Harald Niederreiter, Recent trends in random number and random vector generation, Ann. Oper. Res. 31 (1991), no. 1-4, 323–345. Stochastic programming, Part II (Ann Arbor, MI, 1989). MR 1118905, DOI 10.1007/BF02204856 —, 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.
- B. D. Ripley, Computer generation of random variables: a tutorial, Internat. Statist. Rev. 51 (1983), no. 3, 301–319 (English, with French summary). MR 731146, DOI 10.2307/1402590
- B. D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London Ser. A 389 (1983), no. 1796, 197–204. MR 719645
- S. A. Stepanov, The estimation of rational trigonometric sums with prime denominator, Trudy Mat. Inst. Steklov. 112 (1971), 346–371, 389. (errata insert) (Russian). Collection of articles dedicated to Academician Ivan Matveevič Vinogradov on his eightieth birthday. I. MR 0318158
- André Weil, On some exponential sums, Proc. Nat. Acad. Sci. U.S.A. 34 (1948), 204–207. MR 27006, DOI 10.1073/pnas.34.5.204
Additional Information
- © Copyright 1993 American Mathematical Society
- 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