SPECTRAL TEST

                                                                       
    

The spectral test can be applied to all generators where s-dimensional vectors of pseudorandom numbers form a lattice structure. Usually the set of overlapping vectors
displaymath115
is considered. This set exhibits a lattice structure for many pseudorandom number generators such as linear congruential, multiple recursive, lagged-Fibonacci, add-with-carry, subtract-with-borrow generators, combined linear congruential generators and combined multiple recursive generators, see [20, 2, 15, 16, 3].

The spectral test measures the maximal distance tex2html_wrap_inline117 between adjacent parallel hyperplanes, the maximum being taken over all families of parallel hyperplanes that cover all vectors tex2html_wrap_inline119 (see [12, 13]). The notation spectral test is due to Coveyou and MacPherson [4] who used Fourier analysis for the assessment of linear congruential generators (LCGs). Knuth [12] combined Coveyou and MacPherson's theory and lattice considerations to the spectral test where the reciprocal value of the wave number in the Fourier analysis is equal to tex2html_wrap_inline117.


How to calculate the spectral test? An algorithm is based on the dual lattice derived from tex2html_wrap_inline123. The maximal distance is equal to one over the shortest vector in the dual lattice. Various different variants to calculate the shortest vector of a lattice have been implemented (e.g. see [7, 12, 1, 5]).

An efficient algorithm of the spectral test which facilitates the analysis of lattices generated by vectors of successive or non-successive values produced by linear congruential generators with moduli of essentially unlimited sizes was derived by Pierre L`Ecuyer [19]. Recent tables of LCGs with different moduli tex2html_wrap_inline125 and excellent spectral test results up to high dimensions are given in [17]. The latter paper and many other contributions to the spectral test by Pierre L'Ecuyer et. al. are available via internet.

An easy to handle Mathematica package called ShortestVector.m was implemented by Wilberd van der Kallen. Our package SpectralTest.m uses ShortestVector.m and LLLalgorithm.m to calculate normalized spectral tests tex2html_wrap_inline127, for which tex2html_wrap_inline129. The constants tex2html_wrap_inline131 are absolute lower bounds on tex2html_wrap_inline117 based on Hermite constants for tex2html_wrap_inline135 [12, p. 105,]. Lower bounds tex2html_wrap_inline131 for dimensions s > 8 are given in [17].

Simple examples:

Consider the ``baby'' LCG(256,a,1,0) with a = 85, 101, 61, 237. These LCGs exhibit spectral tests tex2html_wrap_inline141 0.3162, 0.1162, 0.0790, 0.0632 and normalized spectral tests tex2html_wrap_inline143 0.1839, 0.5003, 0.7357, 0.9196 in dimension two. The set tex2html_wrap_inline145 generates the following lattice structures.


tabular34

Many LCGs have been proposed in terms of their good spectral test results up to high dimensions (e.g. see [11, 13, 14, 18, 17, 10, 8, 9]).

A collection of selected linear pseudorandom number that were implemented in commercial software, used in applications, and some of which have extensively been tested is given in [6]. The latter paper contains spectral tests up to dimension 8 and zooms into the unit-square which exhibit the lattice structure of the generators.

References

1
L. Afflerbach and G. Gruber. Assessment of random number generators in high accuracy. In S. Morito, H. Sakasegawa, M. Fushimi, and K. Nakano, editors, New Directions in Simulation for Manufacturing and Communications, pages 128-133. OR Society of Japan, 1994.

2
R. Couture and P. L'Ecuyer. On the lattice structure of certain linear congruential sequences related to AWC/SWB generators. Math. Comp., 62:799-808, 1994.

3
R. Couture and P. L'Ecuyer. Distribution Properties of Multiply-with-Carry Random Number Generators. Math. Comp., 66:591-607, 1997.

4
R.R. Coveyou and R.D. MacPherson. Fourier analysis of uniform random number generators. J. Assoc. Comput. Mach., 14:100-119, 1967.

5
U. Dieter. How to calculate shortest vectors in a lattice. Math. Comp., 29:827-833, 1975.

6
K. Entacher. A collection of selected pseudorandom number generators with linear structures. Technical report, Dept. of Mathematics University of Salzburg, 1997.

Abstract and postscript file available.

7
U. Fincke and M. Pohst. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comp., 44:463-471, 1985.

8
G.S. Fishman. Multiplicative congruential random number generators with modulus tex2html_wrap_inline282: an exhaustive analysis for tex2html_wrap_inline284 and a partial analysis for tex2html_wrap_inline286. Math. Comp., 54:331-344, 1990.

9
G.S. Fishman. Monte Carlo: Concepts, Algorithms, and Applications, volume 1 of Springer Series in Operation Research. Springer, New York, 1996.

10
G.S. Fishman and L.R. Moore. An exhaustive analysis of multiplicative congruential random number generators with modulus tex2html_wrap_inline288. SIAM J. Sci. Statist. Comput., 7:24-45, 1986. See erratum, ibid., 7:1058, 1986.

11
D. Hoaglin. Theoretical Properties of Congruential Random-Number Generators: An Empirical View. Memorandum NS-340. Harvard University, Department of Statistics, 1976.

12
D.E. Knuth. The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 2nd edition, 1981.

13
P. L'Ecuyer. Efficient and portable combined random number generators. Comm. ACM, 31:742-749 and 774, 1988.

14
P. L'Ecuyer. Random numbers for simulation. Comm. ACM, 33:85-97, 1990.

15
P. L'Ecuyer. Combined Multiple Recursive Random Number Generators. Operations Research, 44:816-822, 1996.

16
P. L'Ecuyer. Bad Lattice Structures for Vectors of Non-Successive Values Produced by Some Linear Recurrences. INFORMS Journal on Computing, 9:57-60, 1997.

17
P. L'Ecuyer. Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure, Math. Comp. 1999 to appear.

18
P. L'Ecuyer, F. Blouin, and R. Couture. A Search for Good Multiple Recursive Generators. ACM Trans. on Modeling and Computer Simulation, 3:87-98, 1993.

19
P. L'Ecuyer and R. Couture. An Implementation of the Lattice and Spectral Tests for Multiple Recursive Linear Random Number Generators. INFORMS Journal on Computing., 9, 1997. to appear.

20
S. Tezuka, P. L'Ecuyer, and R. Couture. On Add-with-Carry and Subtract-with-Borrow Random Number Generators. ACM Trans. on Modeling and Computer Simulation, 3:315-331, 1993.


Overview * Team * Generators * Tests * News * Literature * Links



Karl Entacher
Mon Jun 23 11:00:44 MET DST 1997