Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Lower bounds for the discrepancy of inversive congruential pseudorandom numbers


Author: Harald Niederreiter
Journal: Math. Comp. 55 (1990), 277-287
MSC: Primary 65C10; Secondary 11K45
MathSciNet review: 1023766
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The inversive congruential method is a uniform pseudorandom number generator which was introduced recently. For a prime modulus p the discrepancy $ D_p^{(k)}$ of k-tuples of successive pseudorandom numbers generated by this method determines the statistical independence properties of these pseudorandom numbers. It was shown earlier by the author that

$\displaystyle D_p^{(k)} = O({p^{ - 1/2}}{(\log p)^k})\quad {\text{for}}\;2 \leq k < p.$

Here it is proved that this bound is essentially best possible. In fact, for a positive proportion of the admissible parameters in the inversive congruential method the discrepancy $ D_p^{(k)}$ is at least of the order of magnitude $ {p^{ - 1/2}}$ for all $ k \geq 2$.

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


Similar Articles

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

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


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1990-1023766-0
PII: S 0025-5718(1990)1023766-0
Article copyright: © Copyright 1990 American Mathematical Society