Maintained by  Karl.Entacher@fh-salzburg.ac.at  

Spectral Test Server

 

This page is no longer active. Please write to Karl Entacher, Salzburg Polytechnical University to obtain the packages mentioned below. The present site provides information and source code for the spectral test of linear congruential random number generators. It has been designed by Karl Entacher within Peter Hellekalek's pLab project. This part of the pLab project is supported by the Austrian National Bank, Project No. 7576 and the Austrian Science Fund (FWF), Project S8303-MAT. For basic informations on the spectral test read the section below.

You may choose the following items from the menue:

• LLL-Spectral Test gives information on the LLL-approximation of the original spectral test. The LLL-version allows very fast searches for good lattices parameters.
• C - Source: provides information on the implementation of the LLL - Spectral Test in C and examples of source code.
• Math - Source: contains a Mathematica package to calculate spectral tests for linear congruential- and multiple recursive generators. The Mathematica version can for example be used to verify results obtained by the C-version.

Spectral Test Basics

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

Derived from the original form of the spectral test, Peter Hellekalek proposed the general notion of weighted spectral test, which is not limited to random number generators with lattice structures.

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 -- advanced version. Technical report, Dept. of Mathematics University of Salzburg, 1999.

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., 68:249-260, 1999.

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:57-60, 1997.

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.