Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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.

References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society