In the last section we have rejected physical devices in favor of deterministic methods as source of (pseudo-) random numbers. Now, let us take a closer look at some typical algorithms and introduce the notations used in the thesis.
We will treat a generator as an algorithm that produces a
number in [0,1[ on each call. Typically, the algorithms themselves will produce integers in
some
range [0,per-1]
which can be transformed to [0,1[ by
dividing each
number by per.
However, in most applications the user will need a sequence of random vectors in the
s-dimensional unit
cube 
. Such vectors can either be obtained by special pseudorandom vector
generators,
or by
grouping s onedimensional random numbers to form a single vector.
In this thesis we will only discuss the second method.
In principal there exist as many algorithms for generating a sequence of N PRNs as there exist sequences since any enumeration of N PRNs actually is an algorithmic description of this sequence. However, in practice we will have to offer a short and efficient method for calculating the whole sequence when given only initial values. This is what is really meant by the term pseudorandom number generator.
We have to be careful since more complicated algorithms will not necessarily lead to 'better' pseudorandom numbers. This has been illustrated by a nice example in Knuth [26, p.4,] with the 'super-random' number generator ``algorithm K". Knuth shows that this generator can have a very short period. The device actually gives only one PRN when the initial value is set to 6065038420, which is a fixed point of the algorithm.
Since any computer-implemented device will show a periodical behavior due to its finite
state space, the maximal possible period length should be regarded as an important
quality criterion. However, the simple generator
gives a PRN sequence with period per that can be chosen to be any integer that fits into
the
computer's memory. Without doubt, the sequence will, in almost all cases, not be what we
would
like to call an pseudorandom sequence of numbers in the sense of the definition
given in the last section.
We thus have to look for methods that combine both, a long period as well as
'random'
behavior. Excellent surveys on the most important methods for which a detailed theoretical
analysis
has been done are L'Ecuyer [28] and Niederreiter
[38]. We will concentrate on LCGs, the traditional 'workhorse' in the field of
stochastic simulation, ICGs and EICGs. LCGs are linear
generators, i.e. the algorithm uses linear transformations, whereas ICGs and EICGs are
inversive. The later have been introduced by Eichenauer-Herrman and Lehn in a series of papers.
We refer the interested reader to [8] and [10].
Tables of parameters that yield maximal period length for ICGs can be found in [22]. Implementations in ANSI C can be found on the WEB server [2] of the PLAB group in Salzburg, Austria. The next section includes some of the results of the theoretical analysis and will further explain our restriction to these methods.
We have used the following parametrizations for the empirical tests in Chapter 4 because they seem to give a good spot check on the used methods:
, short ``EICG1"
, short ``EICG7"
, short ``ICG"
, recommended by Fishman and Moore in
[14]
, the ANSI C system generator
, the ``minimal standard", see [39]
known as ``RANDU", see [39]
. RANDU only produces some 
different numbers. Fast
implementations are even possible on 32-bit computers. Without any further knowledge about their
application these
generators should be treated as being equally good sources of 'randomness'.
A very interesting approach in order to get longer sequences, the so-called compound method which uses some basic generators of the type LCG, EICG or ICG and adds their output modulo one, will not be discussed in this paper. Theoretical analysis has shown that the compound method somewhat preserves the properties of the single generators. A combination of inversive methods will also show typical 'inversive behavior'. We refer the interested reader to [12].