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), 343354 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 twodimensional 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

L. Afflerbach, Lineare KongruenzGeneratoren zur Erzeugung von PseudoZufallszahlen und ihre Gitterstruktur, Dissertation, Technische Hochschule Darmstadt, 1983.
 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, Pseudorandom numbers. The exact distribution of pairs, Math. Comp. 25 (1971), 855–883. MR 298727, DOI 10.1090/S00255718197102987278 U. Dieter & J. H. Ahrens, Uniform Random Numbers, Inst. f. Math. Stat., Technische Hochschule Graz, 1974.
 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., AddisonWesley Series in Computer Science and Information Processing, AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 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 pseudorandom numbers generated by the linear congruential method. II, Math. Comp. 28 (1974), 1117–1132. MR 457391, DOI 10.1090/S00255718197404573918
 Harald Niederreiter, QuasiMonte Carlo methods and pseudorandom numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S000299041978145327
 B. D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London Ser. A 389 (1983), no. 1796, 197–204. MR 719645
Additional Information
 © Copyright 1989 American Mathematical Society
 Journal: Math. Comp. 53 (1989), 343354
 MSC: Primary 65C10; Secondary 11K45
 DOI: https://doi.org/10.1090/S00255718198909681472
 MathSciNet review: 968147