Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Inversive congruential pseudorandom numbers: distribution of triples

Authors: Jürgen Eichenauer-Herrmann and Harald Niederreiter
Journal: Math. Comp. 66 (1997), 1629-1644
MSC (1991): Primary 65C10; Secondary 11K45
MathSciNet review: 1423072
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper deals with the inversive congruential method with power of two modulus $ m $ for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that, on the average over the parameters in the inversive congruential method, the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude between $ m^{-1/2} $ and $ m^{-1/2}(\log m)^3 $. The method of proof relies on a detailed discussion of the properties of certain exponential sums.

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

  • 1. J. Eichenauer, J. Lehn, and A. Topuzo[??]glu, A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp. 51 (1988), 757-759. MR 89i:65007
  • 2. J. Eichenauer-Herrmann, Inversive congruential pseudorandom numbers: a tutorial, Internat. Statist. Rev. 60 (1992), 167-176.
  • 3. -, Pseudorandom number generation by nonlinear methods, Internat. Statist. Rev. 63 (1995), 247-255.
  • 4. -, Equidistribution properties of inversive congruential pseudorandom numbers with power of two modulus, Metrika 44 (1996), 199-205. CMP 97:04
  • 5. -, Improved upper bounds for the discrepancy of pairs of inversive congruential pseudorandom numbers with power of two modulus, Preprint.
  • 6. J. Eichenauer-Herrmann and H. Niederreiter, On the discrepancy of quadratic congruential pseudorandom numbers, J. Comput. Appl. Math. 34 (1991), 243-249. MR 92c:65010
  • 7. -, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus, Math. Comp. 58 (1992), 775-779. MR 92i:65018
  • 8. -, Kloosterman-type sums and the discrepancy of nonoverlapping pairs of inversive congruential pseudorandom numbers, Acta Arith. 65 (1993), 185-194. MR 94f:11071
  • 9. -, Lower bounds for the discrepancy of triples of inversive congruential pseudorandom numbers with power of two modulus, Monatsh. Math. (to appear).
  • 10. 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 24:A1732
  • 11. P. L'Ecuyer, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77-120. MR 95k:65007
  • 12. R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, MA, 1983. MR 86c:11106
  • 13. H. Niederreiter, Pseudo-random numbers and optimal coefficients, Adv. Math. 26 (1977), 99-181. MR 57:16238
  • 14. -, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), 135-144. MR 90e:65008
  • 15. -, Recent trends in random number and random vector generation, Ann. Oper. Res. 31 (1991), 323-345. MR 92h:65010
  • 16. -, Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, PA, 1992. MR 93h:65008
  • 17. -, New developments in uniform pseudorandom number and vector generation, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P.J.-S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, Springer, New York, 1995, pp. 87-120.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65C10, 11K45

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

Additional Information

Jürgen Eichenauer-Herrmann
Affiliation: Fachbereich Mathematik, Technische Hochschule, Schloßgartenstraße 7, D–64289 Darmstadt, Germany

Harald Niederreiter
Affiliation: Institut für Informationsverarbeitung, Österr. Akademie der Wissenschaften, Sonnenfelsgasse 19, A–1010 Wien, Austria

Keywords: Uniform pseudorandom numbers, inversive congruential method, statistical independence, discrepancy of triples, exponential sums
Received by editor(s): April 12, 1996
Received by editor(s) in revised form: August 23, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society