Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus
HTML articles powered by AMS MathViewer
- by Jürgen Eichenauer-Herrmann and Harald Niederreiter PDF
- Math. Comp. 58 (1992), 775-779 Request permission
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
- 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 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 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
- Hans Salié, Über die Kloostermanschen Summen $S(u,v;q)$, Math. Z. 34 (1932), no. 1, 91–109 (German). MR 1545243, DOI 10.1007/BF01180579
Additional Information
- © Copyright 1992 American Mathematical Society
- 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