`    `

# 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

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 between adjacent parallel hyperplanes, the maximum being taken over all families of parallel hyperplanes that cover all vectors (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 .

How to calculate the spectral test? An algorithm is based on the dual lattice derived from . 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 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 , for which . The constants are absolute lower bounds on based on Hermite constants for [12, p. 105,]. Lower bounds 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 0.3162, 0.1162, 0.0790, 0.0632 and normalized spectral tests 0.1839, 0.5003, 0.7357, 0.9196 in dimension two. The set generates the following lattice structures.

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 : an exhaustive analysis for and a partial analysis for . 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 . 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