The exact determination of rectangle discrepancy for linear congruential pseudorandom numbers

Authors:
Lothar Afflerbach and Rainer Weilbächer

Journal:
Math. Comp. **53** (1989), 343-354

MSC:
Primary 65C10; Secondary 11K45

DOI:
https://doi.org/10.1090/S0025-5718-1989-0968147-2

MathSciNet review:
968147

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**L. Afflerbach,*Lineare Kongruenz-Generatoren zur Erzeugung von Pseudo-Zufallszahlen und ihre Gitterstruktur*, Dissertation, Technische Hochschule Darmstadt, 1983.**[2]**W. A. Beyer, "Lattice structure and reduced bases of random vectors generated by linear recurrences," in*Applications of Number Theory to Numerical Analysis*(S. K. Zaremba, ed.), Academic Press, New York, 1972, pp. 361-370. MR**0351032 (50:3523)****[3]**R. R. Coveyou & R. D. MacPherson, "Fourier analysis of uniform random number generators,"*J. Assoc. Comput. Mach.*, v. 14, 1967, pp. 100-119. MR**0221727 (36:4779)****[4]**U. Dieter, "Pseudo-random numbers: The exact distribution of pairs,"*Math. Comp.*, v. 25, 1971, pp. 855-883. MR**0298727 (45:7776)****[5]**U. Dieter & J. H. Ahrens,*Uniform Random Numbers*, Inst. f. Math. Stat., Technische Hochschule Graz, 1974.**[6]**E. Hlawka, "Zur angenäherten Berechnung mehrfacher Integrale,"*Monatsh. Math.*, v. 66, 1962, pp. 140-151. MR**0143329 (26:888)****[7]**D. E. Knuth,*The Art of Computer Programming*, Vol. II, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR**0378456 (51:14624)****[8]**G. Marsaglia, "Random numbers fall mainly in the planes,"*Proc. Nat. Acad. Sci. U.S.A.*, v. 61, 1968, pp. 25-28. MR**0235695 (38:3998)****[9]**G. Marsaglia, "The structure of linear congruential sequences," in*Applications of Number Theory to Numerical Analysis*(S. K. Zaremba, ed.), Academic Press, New York, 1972, pp. 249-285. MR**0411115 (53:14854)****[10]**H. Niederreiter, "On the distribution of pseudo-random numbers generated by the linear congruential method. III,"*Math. Comp.*, v. 30, 1976, pp. 571-597. MR**0457392 (56:15597b)****[11]**H. Niederreiter, "Quasi-Monte Carlo methods and pseudo-random numbers,"*Bull. Amer. Math. Soc.*, v. 84, 1978, pp. 957-1041. MR**508447 (80d:65016)****[12]**B. D. Ripley, "The lattice structure of pseudo-random number generators,"*Proc. Roy. Soc. London Ser. A*, v. 389, 1983, pp. 197-204. MR**719645 (85i:65010)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65C10,
11K45

Retrieve articles in all journals with MSC: 65C10, 11K45

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1989-0968147-2

Article copyright:
© Copyright 1989
American Mathematical Society