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
This part of the pLab project is supported by the
Austrian National Bank,
Project No. 7576 and the
Austrian Science Fund (FWF),
For basic informations on the spectral test read the
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:
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  who
used Fourier analysis for the assessment of linear congruential generators
Knuth  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,
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
Recent tables of LCGs with different moduli
and excellent spectral test results up to high dimensions are given in
. 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
ShortestVector.m was implemented by
Wilberd van der Kallen.
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 .
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]).
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 . The latter paper
contains spectral tests up to dimension 8 and zooms into the
unit-square which exhibit the lattice structure of the generators.
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.
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.
R. Couture and P. L'Ecuyer.
Distribution Properties of Multiply-with-Carry Random
Math. Comp., 66:591-607, 1997.
R.R. Coveyou and R.D. MacPherson.
Fourier analysis of uniform random number generators.
J. Assoc. Comput. Mach., 14:100-119, 1967.
How to calculate shortest vectors in a lattice.
Math. Comp., 29:827-833, 1975.
A collection of selected pseudorandom number generators with linear
structures -- advanced version.
Technical report, Dept. of Mathematics University of Salzburg, 1999.
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.
Multiplicative congruential random number generators with modulus
: an exhaustive analysis for and a partial analysis for
Math. Comp., 54:331-344, 1990.
Monte Carlo: Concepts, Algorithms, and Applications,
volume 1 of Springer Series in Operation Research.
Springer, New York, 1996.
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.
Theoretical Properties of Congruential Random-Number
Generators: An Empirical View.
Memorandum NS-340. Harvard University, Department of Statistics,
The Art of Computer Programming, volume 2: Seminumerical
Addison-Wesley, Reading, MA, 2nd edition, 1981.
Efficient and portable combined random number generators.
Comm. ACM, 31:742-749 and 774, 1988.
Random numbers for simulation.
Comm. ACM, 33:85-97, 1990.
Combined Multiple Recursive Random Number Generators.
Operations Research, 44:816-822, 1996.
Bad Lattice Structures for Vectors of Non-Successive
Values Produced by Some Linear Recurrences.
INFORMS Journal on Computing, 9:57-60, 1997.
Tables of Linear Congruential Generators of Different
Sizes and Good Lattice Structure.
Math. Comp., 68:249-260, 1999.
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,
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.
S. Tezuka, P. L'Ecuyer, and R. Couture.
On Add-with-Carry and Subtract-with-Borrow Random Number
ACM Trans. on Modeling and Computer Simulation,