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
DOI:
https://doi.org/10.1090/S0025-5718-1992-1122066-X
MathSciNet review:
1122066
Full-text PDF Free Access
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.
- 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, 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 https://doi.org/10.1090/S0025-5718-1988-0958641-1
- Harald Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), no. 185, 135–144. MR 971407, DOI https://doi.org/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 https://doi.org/10.1090/S0025-5718-1990-1023766-0
- Hans Salié, Über die Kloostermanschen Summen $S(u,v;q)$, Math. Z. 34 (1932), no. 1, 91–109 (German). MR 1545243, DOI https://doi.org/10.1007/BF01180579
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