On the distribution of pseudo-random numbers generated by the linear congruential method. III

Niederreiter, Harald

doi:10.1090/S0025-5718-1976-0457392-1

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

An Introduction to the Theory of Numbers

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