Multiplicative congruential random number generators with modulus : an exhaustive analysis for and a partial analysis for

Author:
George S. Fishman

Journal:
Math. Comp. **54** (1990), 331-344

MSC:
Primary 65C10; Secondary 11K45

DOI:
https://doi.org/10.1090/S0025-5718-1990-0993929-9

MathSciNet review:
993929

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents the results of a search to find optimal maximal period multipliers for multiplicative congruential random number generators with moduli and . Here a multiplier is said to be optimal if the distance between adjacent parallel hyperplanes on which *k*-tuples lie does not exceed the minimal achievable distance by more than 25 percent for . This criterion is considerably more stringent than prevailing standards of acceptability and leads to a total of only 132 multipliers out of the more than 536 million candidate multipliers that exist for modulus and to only 42 multipliers in a sample of about 67.1 million tested among the more than candidate multipliers for modulus .

Section 1 reviews the basic properties of multiplicative congruential generators and describes *worst case* performance measures. These include the maximal distance between adjacent parallel hyperplanes, the minimal number of parallel hyperplanes, the minimal distance between *k*-tuples and the discrepancy. For modulus , presents the ten best multipliers and compares their performances with those of two multipliers that have been recommended in the literature. Comparisons using packing measures in the space of *k*-tuples and in the dual space are also made. For modulus , also presents analogous results for the five best multipliers and for two multipliers suggested in the literature.

**[1]**J. H. Ahrens and U. Dieter,*Uniform random numbers*, Technical University of Graz, 1977.**[2]**W. Beyer, Private communication, 1988.**[3]**I. Borosh and H. Niederreiter,*Optimal multipliers for pseudo-random number generation by the linear congruential method*, BIT**23**(1983), 65-74. MR**689604 (84e:65012)****[4]**J. W. S. Cassels,*An introduction to the geometry of numbers*, Springer-Verlag, New York, 1959.**[5]**R. R. Coveyou and R. D. MacPherson,*Fourier analysis of uniform random number generators*, J. Assoc. Comput. Mach.**14**(1967), 100-119. MR**0221727 (36:4779)****[6]**U. Dieter,*Pseudo-random numbers*:*the exact distribution of pairs*, Math. Comp.**25**(1971), 855-883. MR**0298727 (45:7776)****[7]**-,*How to calculate shortest vectors in a lattice*, Math. Comp.**29**(1975), 827-833. MR**0379386 (52:291)****[8]**M. Durst, Private communication, 1989.**[9]**G. S. Fishman and L. R. Moore,*An exhaustive analysis of multiplicative congruential random number generators with modulus*, SIAM J. Sci. Statist. Comput.**7**(1986), 24-45. MR**819455 (87g:65010a)****[10]**D. E. Knuth,*The art of computer programming*:*Semi-numerical algorithms*, 2nd ed., Addison-Wesley, 1981. MR**0378456 (51:14624)****[11]**G. Marsaglia,*Random numbers fall mainly in the plane*, Proc. Nat. Acad. Sci. U.S.A.**61**(1968), 25-28. MR**0235695 (38:3998)****[12]**-,*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)****[13]**H. Niederreiter,*Statistical independence of linear congruential pseudo-random numbers*, Bull. Amer. Math. Soc.**82**(1976), 927-929. MR**0419395 (54:7416)****[14]**-,*Pseudo-random numbers and optimal coefficients*, Adv. Math.**26**(1977), 99-181. MR**0476679 (57:16238)****[15]**-,*The serial test for linear congruential pseudo-random numbers*, Bull. Amer. Math. Soc.**84**(1978), 273-274. MR**0458791 (56:16991)****[16]**-,*Quasi-Monte Carlo methods and pseudo-random numbers*, Bull. Amer. Math. Soc.**84**(1978), 957-1041. MR**508447 (80d:65016)****[17]**-,*The serial test for pseudo-random numbers generated by the linear congruential method*, Numer. Math.**46**(1985), 51-68. MR**777824 (86i:65010)****[18]**C. S. Smith,*Multiplicative pseudo-random number generators with prime modulus*, J. Assoc. Comput. Mach.**18**(1971), 586-593. MR**0295522 (45:4588)**

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-1990-0993929-9

Keywords:
Congruential generator,
discrepancy,
random number generation,
spectral test

Article copyright:
© Copyright 1990
American Mathematical Society