@c -----------------------------------------------
@node Theory
@chapter The Theory behind PRNG
This chapter lists the implemented generators plus a few recommendations
on the parameters.
@menu
* Remarks:: General Remarks
* Definitions:: Generator Definitions and Parameters
* Reading:: Recommended Reading
@end menu
@c -----------------------------------------------
@node Remarks
@section General Remarks
@itemize @bullet
@item On a b-bit computer, the size of the modulus is limited by
@iftex
@tex
$2^{b-1}$,
@end tex
@end iftex
@ifinfo
2^(b-1),
@end ifinfo
@ifhtml
@html
2b-1,
@end html
@end ifhtml
that is 2147483648 on a 32 bit machine or
9223372036854775808 on a 64 bit architecture.
As of version 1.3 the library will reject larger moduli.
@item The library relies on controlled overflow. If you feel
uncomfortable with that, restrict your choice of moduli
to numbers
@iftex
@tex
$< 2^{b-2}$,
@end tex
@end iftex
@ifinfo
< 2^(b-2)
@end ifinfo
@ifhtml
@html
< 2b-2,
@end html
@end ifhtml
and disable the check for power of
two moduli in @code{mult_mod_setup} (@file{support.c}). Run the supplied
validate program if you have doubts about this.
@item The library does @strong{NOT} test if the parameters are valid
for the chosen generator. The user is responsible for
ensuring that the modulus of an inversive generator is
a prime, or that the choice of parameters will lead to
an optimal period length.
@strong{IT IS THUS NOT A GOOD IDEA TO JUST USE ARBITRARY NUMBERS.}
This chapter contains recommended values for all implemented
generator types.
@item Do not base your simulation on a single generator. Even if
you picked a good one you should verify the results using
a completely different generator. There is no generator
whose output does not exhibit an intrinsic structure, so
it is in theory possible that this structure correlates
to the simulation problem and thus leads to a skewed result.
Do not use just other parameters for the verification but
use a different generator type.
@item Small ( < 32767 ) factors will be faster than larger ones.
@end itemize
@c -----------------------------------------------------------
@node Definitions
@section Generator Definitions and Parameters
TeX notation is used.
Most generators operate in the group (or field) Z_p and generate
a sequence y_n, n >= 0 of numbers in Z_p. p is called modulus.
In order to generate U([0,1[) distributed numbers, the y_n
are scaled: x_n = y_n / p.
@emph{Notice:}
If p is prime, one can define the inversion inv() so that
@smallexample
inv(a)*a mod p = 1 (a != 0)
inv(0) = 0
@end smallexample
@sp 1
@subsubheading Generator types
@menu
* EICG:: EICG (explicit inversive congruential generator)
* ICG:: ICG (inversive congruential generator)
* LCG:: LCG (linear congruential generator)
* QCG:: QCG (quadratic congruential generator)
* MT19937:: MT19937 (Mersenne Twister)
* MEICG:: MEICG (modified explicit inversive congruential generator)
* DICG:: DICG (digital inversive congruential generator)
* EXTERNAL:: EXTERNAL (Interface to fixed-parameter generators)
* COMPOUND:: COMPOUND
* SUB:: SUB
* ANTI:: ANTI
* CON:: CON
* AFILE:: AFILE (ASCII file)
* BFILE:: BFILE (Binary file)
@end menu
@c ...........................................................
@node EICG
@subsection EICG (explicit inversive congruential generator)
@itemize @bullet
@item Definition:
@smallexample
y_n = inv(a*(n_0 + n) + b) (mod p) n >= 0
@end smallexample
@item Name (as given to @command{prng_new}):
@code{"eicg(p,a,b,n_0)"}
@item Properties:
@itemize @minus
@item Period length = p.
@item Strong non-linear properties. (e.g. no lattice)
@item Parameter selection not sensitive.
@item @command{prng_is_congruential} is @code{TRUE}
@item @command{prng_can_seed} is @code{TRUE}. @*
The parameter of @command{prng_seed} will be used as
"n" in the next call to @command{get_next}.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{TRUE}.
@end itemize
@item Parameter selection:
Besides a != 0, no restrictions or even suggestions are known.
@item Introduced in:
Eichenauer-Hermann, J. "Statistical independence
of a new class of inversive congruential pseudorandom
numbers", Math. Comp. 60:375-384, 1993
@end itemize
@c ...........................................................
@node ICG
@subsection ICG (inversive congruential generator)
@itemize @bullet
@item Definition:
@smallexample
y_n = a * inv(y_@{n-1@}) + b (mod p) n > 0
@end smallexample
@item Name (as given to @command{prng_new}):
@code{"icg(p,a,b,y_0)"}
@item Properties:
@itemize @minus
@item Period length = p. (for suitable parameters)
@item Strong non-linear properties. (e.g. no lattice)
@item Parameter selection not sensitive.
@item @command{prng_is_congruential} is @code{TRUE}.
@item @command{prng_can_seed} is @code{TRUE}. @*
The parameter of @command{prng_seed} will be used as
@code{y_@{n-1@}} in the next call to @command{get_next}.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con}
are @code{FALSE}.
@end itemize
@item Parameter selection:
To ensure that the period length is p, a and b must be
chosen in a way that x^2 - bx -a (\in F_p[x]) is a
primitive polynomial over F_p.
If ICG(p,a,1) has period length p, then ICG(p,a*c^2,c) will
have period length p, too.
For recommended parameters @pxref{Table_ICG}.
@item Introduced in:
Eichenauer, J. and J. Lehn. "A non-linear congruential
pseudo random number generator", Stat. Papers 27:315-326, 1986
@end itemize
@c ...........................................................
@node LCG
@subsection LCG (linear congruential generator)
@itemize @bullet
@item Definition:
@smallexample
y_n = a * y_@{n-1@} + b (mod p) n > 0
@end smallexample
@item Name (as given to @command{prng_new}):
@code{"lcg(p,a,b,y_0)"}.
@item Properties:
@itemize @minus
@item Period lengths up to p are possible.
@item Strong linear properties.
@item The quality of the PRN depends very strongly on the choice of the parameters.
@item @command{prng_is_congruential} is @code{TRUE}.
@item @command{prng_can_seed} is @code{TRUE}.
The parameter of @command{prng_seed} will be used as
@code{y_@{n-1@}} in the next call to @command{get_next}.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are
@code{TRUE}. @*
Requesting these subsequence may be slow if
large skips are involved and b is not 0.
@end itemize
@item Parameter selection:
If p is a power of 2, then a mod 4 = 1 and b odd will
guarantee period length = p.
If p is prime and b = 0 then any prime-root modulo p as a
will guarantee period length p-1. (y_0 != 0 )
For recommended parameters @pxref{Table_LCG}.
See also the file @file{src/prng_def.h} for a list of frequently
used LCGs.
@emph{Hint:} A rule of thumb suggests not to use more than sqrt(p) random
numbers from an LCG.
References:
Fishman, G.S. "Multiplicative congruential random
number generators ..." Math. Comp. 54:331-344 (1990);
L'Ecuyer, P., "Efficient and portable combined random number
generators" Comm. ACM 31:742-749, 774 (1988)
L'Ecuyer, P., Blouin, F. and Couture R. "A search for
good multiple recursive random number generators" ACM Trans.
Modelling and Computer Simulation 3:87-98 (1993)
@item Introduced by D. H. Lehmer in 1948.
The LCG is @emph{the} classical method. I refer to:
Knuth, D. E. "The Art of Computer Programming, Vol. 2
Seminumerical Algorithms", Addison-Wesley, second edition, 1981
@end itemize
@c ...........................................................
@node QCG
@subsection QCG (quadratic congruential generator)
@itemize @bullet
@item Definition:
@smallexample
y_n = a * y_@{n-1@}^2 + b *y_@{n-1@} + c (mod p) n > 0
@end smallexample
@item Name (as given to @command{prng_new}):
@code{"qcg(p,a,b,c,y0)"}.
@item Properties:
@itemize @minus
@item Period lengths up to p are possible.
@item Weaker linear properties (tuples fall into union of lattices)
@item Reasonable distribution in dimension 2, but not that good in dimension 3.
@item @command{prng_is_congruential} is @code{TRUE}.
@item @command{prng_can_seed} is @code{TRUE}. @*
The parameter of @command{prng_seed} will be used as
@code{y_@{n-1@}} in the next call to @command{get_next}.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{FALSE}.
@end itemize
@item Parameter selection:
If p is a power of 2, then a even, b == a + 1 mod 4, and
c odd will guarantee period length = p.
No table of good parameters has been published.
@item Introduced in:
Knuth, D. E. "The Art of Computer Programming, Vol. 2
Seminumerical Algorithms", Addison-Wesley, second edition, 1981
@end itemize
@c ...........................................................
@node MT19937
@subsection MT19937 (Mersenne Twister)
@itemize @bullet
@c @item Definition:
@item Name (as given to @command{prng_new}):
@code{"mt19937(seed)"}.
@item Properties:
@itemize @minus
@item Period lengths is 2^19937-1.
@item @command{prng_is_congruential} is @code{TRUE}.
@item @command{prng_can_seed} is @code{TRUE}. @*
The parameter of @command{prng_seed} will be used to
seed the array of coefficients.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{FALSE}.
@end itemize
@item Introduced in:
Matsumoto, M. and Nishimura, T.,
"Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
Pseudo-Random Number Generator",
ACM Transactions on Modeling and Computer Simulation,
Vol. 8, No. 1, January 1998, pp 3--30.
@end itemize
@c ...........................................................
@node MEICG
@subsection MEICG (modified explicit inversive congruential generator)
@itemize @bullet
@item Definition:
@smallexample
y_n = n * inv(a*(n_0 + n) + b) (mod p) n >= 0
@end smallexample
@item Name (as given to @command{prng_new}):
@code{"meicg(p,a,b,n_0)"}.
@item Properties:
@itemize @minus
@item Period length = p.
@item @command{prng_is_congruential} is @code{TRUE}.
@item @command{prng_can_seed} is @code{TRUE}.
The parameter of @command{prng_seed} will be used as
"n" in the next call to @command{get_next}.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{FALSE}.
@end itemize
Experimental generator: @strong{USE AT OWN RISK}
@item Parameter selection:
@itemize @minus
@item For prime moduli, a != 0 suffices.
@item It's possible to use a powe of 2 as modulus, which requires
a = 2 (mod 4) and b = 1 (mod 2).
@end itemize
@item Introduced in:
Eichenauer-Hermann, J. "Modified explicit inverive congruential
pseudorandom numbers with power of 2 modulus"
Statistics and Computing 6:31-36 (1996)
@end itemize
@c ...........................................................
@node DICG
@subsection DICG (digital inversive congruential generator)
@itemize @bullet
@item Definition:
@smallexample
y_n = a * inv(y_@{n-1@}) + b (mod p) n > 0
@end smallexample
@strong{All operations are in the field F_@{2^k@} !!}
@item Name (as given to @command{prng_new}):
@code{"dicg(k,a,b,y_0)"}.
@item Properties:
@itemize @minus
@item Period length = 2^k.
@item Strong non-linear properties.
@item Parameters seem not to be sensitive
@item @command{prng_is_congruential} is @code{TRUE}.
@item @command{prng_can_seed} is @code{TRUE}.
The parameter of @command{prng_seed} will be used as
@code{y_@{n-1@}} in the next call to @command{get_next}
@end itemize
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{FALSE}.
@item Parameter selection:
Tricky.
@item Introduced in:
Eichenauer-Herrmann and Niederreiter, "Digital inversive
pseudorandom numbers", ACM Transactions on Modeling and Computer
Simulation, 4:339-349 (1994)
@end itemize
@c ...........................................................
@node EXTERNAL
@subsection EXTERNAL (Interface to fixed-parameter generators)
These generators are included to provide a uniform interface
to a wider range of PRNG. The only enhancements from the
published code is the support for multiple streams of these
generators, as the original code used global variables.
See the file @file{src/external.c} for the references. Included are
@itemize @minus
@item TT800 (a large TSFR by M. Matsumoto)
@item CTG (Combined Tausworthe Generator by P. L'Ecuyer)
@item MRG (Multiple Recursive Generator by P. L'Ecuyer)
@item CMRG (Combined (Multiple Recursive Generator by P. L'Ecuyer)
@end itemize
@c ...........................................................
@node COMPOUND
@subsection COMPOUND
@itemize @bullet
@item Definition:
This is a "meta"-generator which combines a number of
PRNG into one single generator by adding the respective
numbers modulo 1.
@item Name (as given to @command{prng_new}):
@code{"c(generator1,generator2, ...)"}.
Up to @code{PRNG_MAX_COMPOUNDS} generators are permitted.
@var{generatorX} may be any valid generator definition, including
a compound generator.
@item Properties:
@itemize @minus
@item Period length: Least common multiple of the period length's
of the component generators.
@item Generally speaking, most properties of PRNG are preserved
if combining generators of the same type.
@item @command{prng_is_congruential} is @code{FALSE}.
@item @command{prng_can_seed} is @code{TRUE}.
@item The parameters of @command{prng_seed} is used to
seed all seedable component generators.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con}
depend on the underlying generators.
@end itemize
@end itemize
@c ...........................................................
@node SUB
@subsection SUB
@itemize @bullet
@item Definition:
This is a "meta"-generator which takes a subsequence out
of another generator.
@item Name (as given to @command{prng_new}):
@code{"sub(gen,s,i)"}.
The output of "gen" is spliced into s streams, and the
i-th is used. (0 <= i < s)
@item Properties:
@itemize @minus
@item Period length: Typically the period of "gen".
@item Generally speaking, most properties of PRNG are preserved
when taking subsequence.
@item @command{prng_is_congruential} and @command{prng_can_seed} depend on "gen".
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{FALSE}.
@end itemize
@end itemize
@c ...........................................................
@node ANTI
@subsection ANTI
@itemize @bullet
@item Definition:
This is a "meta"-generator wich returns 1-U instead of U as
random number.
@item Name (as given to @command{prng_new}):
@code{"anti(gen)"}.
The output of gen (U) is changed to 1-U.
@end itemize
@c ...........................................................
@node CON
@subsection CON
@itemize @bullet
@item Definition:
This is a "meta"-generator which takes a block of numbers
out of the output of another generator.
@item Name (as given to @command{prng_new}):
@code{"con(gen,l,i)"}.
The output of "gen" is divided into blocks of length l,
and the i-th is used. (0 <= i < l)
@item Properties:
@itemize @minus
@item Period length: The period of "gen".
@item @command{prng_is_congruential} and @command{prng_can_seed} depend on "gen".
@item @command{prng_can_fast_sub } and @command{prng_can_fast_con} are @code{FALSE}.
@end itemize
@end itemize
@c ...........................................................
@node AFILE
@subsection AFILE (ASCII file)
@itemize @bullet
@item Definition :
This generator takes its numbers from the named file. It
expects each number in plain ascii (atof must be able to parse it)
and on its own line. If EOF is reached, a warning is printed to
stderr and reading continues at the beginning of the file.
@item Name (as given to @command{prng_new}):
@code{"afile(some_file_name)"}.
@item Properties:
@itemize @minus
@item @command{prng_is_congruential} is @code{FALSE}.
@item @command{prng_can_seed} is @code{FALSE}.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{FALSE}.
@end itemize
@end itemize
@c ...........................................................
@node BFILE
@subsection BFILE (Binary file)
@itemize @bullet
@item Definition:
This generator takes its numbers from the named file.
In order to get good numbers, the file should contain random bytes.
If EOF is reached, a warning is printed to stderr and reading
continues at the beginning of the file.
@item Name (as given to @command{prng_new}):
@code{"bfile(some_file_name)"}.
@strong{WARNING}:
The conversion between bytes and numbers in [0,1)
is NOT guaranteed to yield the same results on
different computers.
@item Properties:
@itemize @minus
@item @command{prng_is_congruential} is @code{FALSE}.
@item @command{prng_can_seed} is @code{FALSE}.
@item @command{prng_can_fast_sub} and @command{prng_can_fast_con} are @code{FALSE}.
@end itemize
@end itemize
@c -----------------------------------------------------------
@node Reading
@section Recommended Reading
Niederreiter, H. "New developments in uniform pseudorandom number and
vector generation" in "Monte Carlo and Quasi-Monte Carlo Methods
in Scientific Computing", Lecture Notes in Statistics, Springer.
Hellekalek, P. "Inversive pseudorandom number generators: Concepts,
Results and Links"
Eichenauer-Herrmann, J. "Pseudorandom Number Generation by Nonlinear
Methods" Int. Statistical Review 63:247-255 (1995)
L'Ecuyer, P. "Uniform random number generation" Ann. Oper. Res. 53:77-120
(1994)
Wegenkittl, S. "Empirical testing of pseudorandom number generators"
Master's thesis, Universitaet Salzburg, 1995