Linear congruential generators of order K>1

ABSTRACT

We present a class of random number generators defined by a linear congruential recursion of order k ≥ 1, modulo m, and whose period can attain mk - 1. The spectral test can be extended to this class of generators, and permits the computation of the distance between the successive t-dimensional hyperplanes in which lie all the t-tuples of successive values. In terms of the spectral test, these generators could be almost as good as the best regular (order 1) linear congruential generators with modulus close to mk - 1. We discuss the implementation of computer programs to search for maximal period generators of this kind and to apply the (generalized) spectral test. We also present the results of a search to find good vectors of multipliers, for some values of the modulus m, and give an example of a portable implementation.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Measurement, Performance, Theory