On the distribution of pseudo-random numbers generated by the linear congruential method. III
HTML articles powered by AMS MathViewer
- by Harald Niederreiter PDF
- Math. Comp. 30 (1976), 571-597 Request permission
Abstract:
The discrepancy of a sequence of pseudo-random numbers generated by the linear congruential method, both homogeneous and inhomogeneous, is estimated for parts of the period that are somewhat larger than the square root of the modulus. The analogous problem for an arbitrary linear congruential generator modulo a prime is also considered, the result being particularly interesting for maximal period sequences. It is shown that the discrepancy estimates in this paper are best possible apart from logarithmic factors.References
- U. Dieter, Statistical interdependence of pseudo-random numbers generated by the linear congruential method, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 287–317. MR 0353622 G. H. HARDY & E. M. WRIGHT, An Introduction to the Theory of Numbers, 4th ed., Clarendon Press, Oxford, 1960.
- Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
- George Marsaglia, The structure of linear congruential sequences, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 249–285. MR 0411115
- H. G. Meijer and H. Niederreiter, Équirépartition et théorie des nombres premiers, Répartition modulo 1 (Actes Colloq., Marseille-Luminy, 1974) Lecture Notes in Math., Vol. 475, Springer, Berlin, 1975, pp. 104–112 (French). MR 0389819
- Harald Niederreiter, On the distribution of pseudo-random numbers generated by the linear congruential method, Math. Comp. 26 (1972), 793–795. MR 326979, DOI 10.1090/S0025-5718-1972-0326979-5
- Harald Niederreiter, On the distribution of pseudo-random numbers generated by the linear congruential method. II, Math. Comp. 28 (1974), 1117–1132. MR 457391, DOI 10.1090/S0025-5718-1974-0457391-8
- H. Niederreiter, Résultats nouveaux dans la théorie quantitative de l’équirépartition, Répartition modulo 1 (Actes Colloq., Marseille-Luminy, 1974) Lecture Notes in Math., Vol. 475, Springer, Berlin, 1975, pp. 132–154 (French). MR 0389822
- H. Niederreiter, Some new exponential sums with applications to pseudo-random numbers, Topics in number theory (Proc. Colloq., Debrecen, 1974) Colloq. Math. Soc. János Bolyai, Vol. 13, North-Holland, Amsterdam, 1976, pp. 209–232. MR 0447141
- H. Niederreiter, On the cycle structure of linear recurring sequences, Math. Scand. 38 (1976), no. 1, 53–77. MR 406918, DOI 10.7146/math.scand.a-11616
- H. Niederreiter and Walter Philipp, Berry-Esseen bounds and a theorem of Erdős and Turán on uniform distribution $\textrm {mod}\ 1$, Duke Math. J. 40 (1973), 633–649. MR 337873
- Robert C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201–209. MR 184406, DOI 10.1090/S0025-5718-1965-0184406-1
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Math. Comp. 30 (1976), 571-597
- MSC: Primary 10K05; Secondary 65C10
- DOI: https://doi.org/10.1090/S0025-5718-1976-0457392-1
- MathSciNet review: 0457392