Home
SpectralTest Home
LLLSpectral Test
CSource
MathSource
Maintained by
Karl.Entacher@fhsalzburg.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 S8303MAT.
For basic informations on the spectral test read the
section below.


You may choose the following items from the menue:
 LLLSpectral Test
gives information on the LLLapproximation of
the original spectral test.
The LLLversion 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 Cversion.
Spectral Test Basics
The classical spectral test can be applied to all generators
where sdimensional 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, laggedFibonacci,
addwithcarry, subtractwithborrow 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 nonsuccessive 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
unitsquare 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
128133. 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:799808, 1994.
 3

R. Couture and P. L'Ecuyer.
Distribution Properties of MultiplywithCarry Random
Number Generators.
Math. Comp., 66:591607, 1997.
 4

R.R. Coveyou and R.D. MacPherson.
Fourier analysis of uniform random number generators.
J. Assoc. Comput. Mach., 14:100119, 1967.
 5

U. Dieter.
How to calculate shortest vectors in a lattice.
Math. Comp., 29:827833, 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:463471, 1985.
 8

G.S. Fishman.
Multiplicative congruential random number generators with modulus
: an exhaustive analysis for and a partial analysis for
.
Math. Comp., 54:331344, 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:2445, 1986.
See erratum, ibid., 7:1058, 1986.
 11

D. Hoaglin.
Theoretical Properties of Congruential RandomNumber
Generators: An Empirical View.
Memorandum NS340. Harvard University, Department of Statistics,
1976.
 12

D.E. Knuth.
The Art of Computer Programming, volume 2: Seminumerical
Algorithms.
AddisonWesley, Reading, MA, 2nd edition, 1981.
 13

P. L'Ecuyer.
Efficient and portable combined random number generators.
Comm. ACM, 31:742749 and 774, 1988.
 14

P. L'Ecuyer.
Random numbers for simulation.
Comm. ACM, 33:8597, 1990.
 15

P. L'Ecuyer.
Combined Multiple Recursive Random Number Generators.
Operations Research, 44:816822, 1996.
 16

P. L'Ecuyer.
Bad Lattice Structures for Vectors of NonSuccessive
Values Produced by Some Linear Recurrences.
INFORMS Journal on Computing, 9:5760, 1997.
 17

P. L'Ecuyer.
Tables of Linear Congruential Generators of Different
Sizes and Good Lattice Structure.
Math. Comp., 68:249260, 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:8798,
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:5760, 1997.
 20

S. Tezuka, P. L'Ecuyer, and R. Couture.
On AddwithCarry and SubtractwithBorrow Random Number
Generators.
ACM Trans. on Modeling and Computer Simulation,
3:315331, 1993.
