next up previous
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 tex2html_wrap_inline487, let tex2html_wrap_inline489 if c=0 and tex2html_wrap_inline493 if tex2html_wrap_inline495. In other words, tex2html_wrap_inline497 equals the number tex2html_wrap_inline499 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 tex2html_wrap_inline509. Then the congruence
equation82
defines an inversive congruential generator. We denote this generator by
displaymath511
It produces a sequence tex2html_wrap_inline513 in the set tex2html_wrap_inline515 Pseudorandom numbers tex2html_wrap_inline517 in [0,1[ are obtained by the normalization tex2html_wrap_inline521

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) tex2html_wrap_inline523, tex2html_wrap_inline525, in a region near the point (0.5, 0.5) are shown.


tabular91

Figure 1: ICG(tex2html_wrap_inline527, 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 tex2html_wrap_inline535, tex2html_wrap_inline537, an additive term tex2html_wrap_inline539, and an initial value tex2html_wrap_inline541 in tex2html_wrap_inline543. Then
 equation106
defines a sequence of pseudorandom number s in tex2html_wrap_inline515 As before, we put tex2html_wrap_inline517:= tex2html_wrap_inline549, tex2html_wrap_inline525, to obtain pseudorandom number s in [0,1[. We shall denote this generator by
displaymath555

In the definition of EICG(tex2html_wrap_inline557), the additive term b is superfluous. It is easy to see that the two generators EICG(tex2html_wrap_inline557) and EICG(tex2html_wrap_inline563), with
displaymath565
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 tex2html_wrap_inline569 be distinct prime numbers, each tex2html_wrap_inline571. For each index j, tex2html_wrap_inline575, let tex2html_wrap_inline577 be a sequence of elements of tex2html_wrap_inline579 that is purely periodic with period length tex2html_wrap_inline581. In other words,
displaymath583
Let tex2html_wrap_inline585 denote the related sequence of pseudorandom number s in [0,1[, where
displaymath589
A sequence tex2html_wrap_inline591 of compound pseudorandom number s in [0,1[ is defined by the congruence
equation131
It is elementary to see that the period of the sequence tex2html_wrap_inline591 equals M:= tex2html_wrap_inline599 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 tex2html_wrap_inline523, tex2html_wrap_inline525, have been computed. The period of this generator is M= 2158801621.


tabular140

Figure 2: A Combined ICG with Three Components


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


next up previous
Next: THEORETICAL RESULTS Up: INVERSIVE PSEUDORANDOM NUMBER GENERATORS: Previous: INTRODUCTION

Peter Hellekalek