The exact determination of rectangle discrepancy for linear congruential pseudorandom numbers

Afflerbach, Lothar; Weilbächer, Rainer

doi:10.1090/S0025-5718-1989-0968147-2

The exact determination of rectangle discrepancy for linear congruential pseudorandom numbers
HTML articles powered by AMS MathViewer

by Lothar Afflerbach and Rainer Weilbächer PDF

Math. Comp. 53 (1989), 343-354 Request permission

Abstract:

Up to now, the rectangle discrepancy of linear congruential pseudorandom number generators could be exactly calculated only in some simple cases for a small number of generated points. Here an algorithm for the exact determination of the two-dimensional rectangle discrepancy is presented which is practicable for large generators and requires less computation time. The algorithm is based on special properties of linear congruential generators.

References

Lineare Kongruenz-Generatoren zur Erzeugung von Pseudo-Zufallszahlen und ihre Gitterstruktur

W. A. Beyer, Lattice structure and reduced bases of random vectors generated by linear recurrences, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 361–370. MR 0351032
R. R. Coveyou and R. D. Macpherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100–119. MR 221727, DOI 10.1145/321371.321379
U. Dieter, Pseudo-random numbers. The exact distribution of pairs, Math. Comp. 25 (1971), 855–883. MR 298727, DOI 10.1090/S0025-5718-1971-0298727-8

Uniform Random Numbers

Edmund Hlawka, Zur angenäherten Berechnung mehrfacher Integrale, Monatsh. Math. 66 (1962), 140–151 (German). MR 143329, DOI 10.1007/BF01387711
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
George Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. U.S.A. 61 (1968), 25–28. MR 235695, DOI 10.1073/pnas.61.1.25
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
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
Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S0002-9904-1978-14532-7
B. D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London Ser. A 389 (1983), no. 1796, 197–204. MR 719645