Next: THEORETICAL RESULTS Up: INVERSIVE PSEUDORANDOM NUMBER GENERATORS: Previous: INTRODUCTION

INVERSIVE GENERATORS

We discuss three concepts of inversive methods, inversive congruential generators, explicit-inversive congruential generators, and combinations of these algorithms.

Inversive methods may be defined even for composite moduli. In view of their outstanding performance, we shall only consider prime moduli. Elaborate theoretical analysis has shown that the composite case is of little practical interest. We refer the reader to Niederreiter (1995a) for a comprehensive survey of these results.

For a given prime number p, and for , let if c=0 and if . In other words, equals the number modulo p.

Inversive Congruential Generators

Inversive congruential generators (``ICG'') are due to Eichenauer and Lehn (1986). We have to choose the modulus p, a multiplier a, an additive term b, and an initial value . Then the congruence

defines an inversive congruential generator. We denote this generator by

It produces a sequence in the set Pseudorandom numbers in [0,1[ are obtained by the normalization

A prominent feature of the ICG with prime modulus is the absence of any lattice structure, in sharp contrast to linear congruential generators (``LCG''). In the following scatter plot, all possible points (``nonoverlapping pairs'' of consecutive pseudorandom number s) , , in a region near the point (0.5, 0.5) are shown.

Figure 1: ICG(, 1288490188, 1, 0)

The proper choice of the parameters a and b will be discussed in Section 3. An important feature of the ICG with respect to implementation is the ``mother-son'' principle, see Section 5.

Explicit Inversive Congruential Generators

Roughly speaking, the EICG is the ``easy-going brother'' of the ICG. It is due to Eichenauer-Herrmann (1993a). As we shall see, the EICG is easier to handle in practice, for example when producing independent substreams. The cost is a slightly smaller maximal sample size, as our empirical tests have shown, see Figure 6 in Section 4.

We choose a prime number p, a multiplier , , an additive term , and an initial value in . Then

defines a sequence of pseudorandom number s in As before, we put := , , to obtain pseudorandom number s in [0,1[. We shall denote this generator by

In the definition of EICG(), the additive term b is superfluous. It is easy to see that the two generators EICG() and EICG(), with

produce identical output. Hence, in most of our tests, we shall put b=0.

Compound generators

Eichenauer-Herrmann (1993b, 1994a) has introduced a simple technique to combine inversive generators, the compound approach.

Let be distinct prime numbers, each . For each index j, , let be a sequence of elements of that is purely periodic with period length . In other words,

Let denote the related sequence of pseudorandom number s in [0,1[, where

A sequence of compound pseudorandom number s in [0,1[ is defined by the congruence

It is elementary to see that the period of the sequence equals M:= We shall write cICG for a compound ICG and cEICG for a compound EICG.

The compound approach allows to combine ICG and EICG, provided they have full period. This method has important advantages: we may obtain very long periods easily, modular operations may be carried out with relatively small moduli, increasing the effectiveness of our computations, and the good correlation structure of the ICG and EICG is preserved. For the latter statement, see Section 3.

We present a scatter plot of a combined ICG, c(ICG(1031,55,1,0), ICG(1033,103,1,0), ICG(2027, 66,1,0)). All possible points , , have been computed. The period of this generator is M= 2158801621.

Figure 2: A Combined ICG with Three Components

Overview * Team * Generators * Tests * News * Literature * Links

Next: THEORETICAL RESULTS Up: INVERSIVE PSEUDORANDOM NUMBER GENERATORS: Previous: INTRODUCTION

Peter Hellekalek