Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus

Authors: Jürgen Eichenauer-Herrmann and Harald Niederreiter
Journal: Math. Comp. 58 (1992), 775-779
MSC: Primary 65C10; Secondary 11K45
MathSciNet review: 1122066
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The inversive congruential method with modulus $ m = {2^\omega }$ for the generation of uniform pseudorandom numbers has recently been introduced. The discrepancy $ D_{m/2}^{(k)}$ of k-tuples of consecutive pseudorandom numbers generated by such a generator with maximal period length $ m/2$ is the crucial quantity for the analysis of the statistical independence properties of these pseudorandom numbers by means of the serial test. It is proved that for a positive proportion of the inversive congruential generators with maximal period length, the discrepancy $ D_{m/2}^{(k)}$ is at least of the order of magnitude $ {m^{ - 1/2}}$ for all $ k \geq 2$. This shows that the bound $ D_{m/2}^{(2)} = O({m^{ - 1/2}}{(\log m)^2})$ established by the second author is essentially best possible.

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

  • [1] J. Eichenauer and J. Lehn, A non-linear congruential pseudo random number generator, Statist. Papers 27 (1986), 315-326. MR 877295 (88i:65014)
  • [2] 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)
  • [3] H. Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), 135-144. MR 971407 (90e:65008)
  • [4] -, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers, Math. Comp. 55 (1990), 277-287. MR 1023766 (91e:65016)
  • [5] H. Salié, Über die Kloostermanschen Summen $ S(u,v;q)$, Math. Z. 34 (1932), 91-109. MR 1545243

Similar Articles

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

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

Additional Information

Keywords: Pseudorandom number generator, inversive congruential method, power of two modulus, discrepancy
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society