The Theory behind PRNG
**********************

This chapter lists the implemented generators plus a few recommendations on the parameters.

General Remarks
===============

  * On a b-bit computer, the size of the modulus is limited by 2^(b-1), 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.

  * The library relies on controlled overflow. If you feel uncomfortable with that, restrict your choice of moduli to numbers < 2^(b-2)

     and disable the check for power of two moduli in mult_mod_setup (support.c). Run the supplied validate program if you have doubts about this.

  * The library does 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.

     IT IS THUS NOT A GOOD IDEA TO JUST USE ARBITRARY NUMBERS.

     This chapter contains recommended values for all implemented generator types.

  * 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.

  * Small ( < 32767 ) factors will be faster than larger ones.

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.

Notice: If p is prime, one can define the inversion inv() so that

        inv(a)*a mod p = 1   (a != 0)
        inv(0) = 0

Generator types
...............

EICG (explicit inversive congruential generator)
------------------------------------------------

  * Definition:

          y_n = inv(a*(n_0 + n) + b) (mod p)      n >= 0

  * Name (as given to prng_new): "eicg(p,a,b,n_0)"

  * Properties:

       - Period length  = p.

       - Strong non-linear properties. (e.g. no lattice)

       - Parameter selection not sensitive.

       - prng_is_congruential is TRUE

       - prng_can_seed is TRUE.
          The parameter of prng_seed will be used as "n" in the next call to get_next.

       - prng_can_fast_sub and prng_can_fast_con are TRUE.

  * Parameter selection: Besides a != 0, no restrictions or even suggestions are known.

  * Introduced in: Eichenauer-Hermann, J. "Statistical independence of a new class of inversive congruential pseudorandom numbers", Math. Comp. 60:375-384, 1993

ICG (inversive congruential generator)
--------------------------------------

  * Definition:

          y_n = a * inv(y_{n-1}) + b (mod p)    n > 0

  * Name (as given to prng_new): "icg(p,a,b,y_0)"

  * Properties:

       - Period length  = p.  (for suitable parameters)

       - Strong non-linear properties. (e.g. no lattice)

       - Parameter selection not sensitive.

       - prng_is_congruential is TRUE.

       - prng_can_seed is TRUE.
          The parameter of prng_seed will be used as y_{n-1} in the next call to get_next.

       - prng_can_fast_sub and prng_can_fast_con are FALSE.

  * 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 see Table_ICG.

  * Introduced in: Eichenauer, J. and J. Lehn. "A non-linear congruential pseudo random number generator", Stat. Papers 27:315-326, 1986

LCG (linear congruential generator)
-----------------------------------

  * Definition:

          y_n = a * y_{n-1} + b (mod p)     n > 0

  * Name (as given to prng_new): "lcg(p,a,b,y_0)".

  * Properties:

       - Period lengths up to p are possible.

       - Strong linear properties.

       - The quality of the PRN depends very strongly on the choice of the parameters.

       - prng_is_congruential is TRUE.

       - prng_can_seed is TRUE. The parameter of prng_seed will be used as y_{n-1} in the next call to get_next.

       - prng_can_fast_sub and prng_can_fast_con are TRUE.

          Requesting these subsequence may be slow if large skips are involved and b is not 0.

  * 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 see Table_LCG.

     See also the file src/prng_def.h for a list of frequently used LCGs.

     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)

  * Introduced by D. H. Lehmer in 1948.

     The LCG is the classical method. I refer to: Knuth, D. E. "The Art of Computer Programming, Vol. 2 Seminumerical Algorithms", Addison-Wesley, second edition, 1981

QCG (quadratic congruential generator)
--------------------------------------

  * Definition:

          y_n = a * y_{n-1}^2 + b *y_{n-1} + c (mod p)     n > 0

  * Name (as given to prng_new): "qcg(p,a,b,c,y0)".

  * Properties:

       - Period lengths up to p are possible.

       - Weaker linear properties (tuples fall into union of lattices)

       - Reasonable distribution in dimension 2, but not that good in dimension 3.

       - prng_is_congruential is TRUE.

       - prng_can_seed is TRUE.
          The parameter of prng_seed will be used as y_{n-1} in the next call to get_next.

       - prng_can_fast_sub and prng_can_fast_con are FALSE.

  * 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.

  * Introduced in:

     Knuth, D. E. "The Art of Computer Programming, Vol. 2 Seminumerical Algorithms", Addison-Wesley, second edition, 1981

MT19937 (Mersenne Twister)
--------------------------

  * Name (as given to prng_new): "mt19937(seed)".

  * Properties:

       - Period lengths is 2^19937-1.

       - prng_is_congruential is TRUE.

       - prng_can_seed is TRUE.
          The parameter of prng_seed will be used to seed the array of coefficients.

       - prng_can_fast_sub and prng_can_fast_con are FALSE.

  * 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.

MEICG (modified explicit inversive congruential generator)
----------------------------------------------------------

  * Definition:

          y_n = n * inv(a*(n_0 + n) + b) (mod p)    n >= 0

  * Name (as given to prng_new): "meicg(p,a,b,n_0)".

  * Properties:

       - Period length  = p.

       - prng_is_congruential is TRUE.

       - prng_can_seed is TRUE. The parameter of prng_seed will be used as "n" in the next call to get_next.

       - prng_can_fast_sub and prng_can_fast_con are FALSE.

     Experimental generator: USE AT OWN RISK

  * Parameter selection:

       - For prime moduli, a != 0 suffices.

       - It's possible to use a powe of 2 as modulus, which requires a = 2 (mod 4) and b = 1 (mod 2).

  * Introduced in:

     Eichenauer-Hermann, J. "Modified explicit inverive congruential pseudorandom numbers with power of 2 modulus" Statistics and Computing 6:31-36 (1996)

DICG (digital inversive congruential generator)
-----------------------------------------------

  * Definition:

          y_n = a * inv(y_{n-1}) + b (mod p)      n > 0

     All operations are in the field F_{2^k} !!

  * Name (as given to prng_new): "dicg(k,a,b,y_0)".

  * Properties:

       - Period length  = 2^k.

       - Strong non-linear properties.

       - Parameters seem not to be sensitive

       - prng_is_congruential is TRUE.

       - prng_can_seed is TRUE. The parameter of prng_seed will be used as y_{n-1} in the next call to get_next

  * prng_can_fast_sub and prng_can_fast_con are FALSE.

  * Parameter selection:

     Tricky.

  * Introduced in:

     Eichenauer-Herrmann and Niederreiter, "Digital inversive pseudorandom numbers", ACM Transactions on Modeling and Computer Simulation, 4:339-349 (1994)

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 src/external.c for the references. Included are

  - TT800 (a large TSFR by M. Matsumoto)

  - CTG   (Combined Tausworthe Generator by P. L'Ecuyer)

  - MRG   (Multiple Recursive Generator by P. L'Ecuyer)

  - CMRG  (Combined (Multiple Recursive Generator by P. L'Ecuyer)

COMPOUND
--------

  * Definition:

     This is a "meta"-generator which combines a number of PRNG into one single generator by adding the respective numbers modulo 1.

  * Name (as given to prng_new): "c(generator1,generator2, ...)".

     Up to PRNG_MAX_COMPOUNDS generators are permitted. GENERATORX may be any valid generator definition, including a compound generator.

  * Properties:

       - Period length: Least common multiple of the period length's of the component generators.

       - Generally speaking, most properties of PRNG are preserved if combining generators of the same type.

       - prng_is_congruential is FALSE.

       - prng_can_seed is TRUE.

       - The parameters of prng_seed is used to seed all seedable component generators.

       - prng_can_fast_sub and prng_can_fast_con depend on the underlying generators.

SUB
---

  * Definition: This is a "meta"-generator which takes a subsequence out of another generator.

  * Name (as given to prng_new): "sub(gen,s,i)".

     The output of "gen" is spliced into s streams, and the i-th is used. (0 <= i < s)

  * Properties:

       - Period length: Typically the period of "gen".

       - Generally speaking, most properties of PRNG are preserved when taking subsequence.

       - prng_is_congruential and prng_can_seed depend on "gen".

       - prng_can_fast_sub and prng_can_fast_con are FALSE.

ANTI
----

  * Definition:

     This is a "meta"-generator wich returns 1-U instead of U as random number.

  * Name (as given to prng_new): "anti(gen)".

     The output of gen (U) is changed to 1-U.

CON
---

  * Definition:

     This is a "meta"-generator which takes a block of numbers out of the output of another generator.

  * Name (as given to prng_new): "con(gen,l,i)".

     The output of "gen" is divided into blocks of length l, and the i-th is used. (0 <= i < l)

  * Properties:

       - Period length: The period of "gen".

       - prng_is_congruential and prng_can_seed depend on "gen".

       - prng_can_fast_sub  and prng_can_fast_con are FALSE.

AFILE (ASCII file)
------------------

  * 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.

  * Name (as given to prng_new): "afile(some_file_name)".

  * Properties:

       - prng_is_congruential is FALSE.

       - prng_can_seed is FALSE.

       - prng_can_fast_sub and prng_can_fast_con are FALSE.

BFILE (Binary file)
-------------------

  * 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.

  * Name (as given to prng_new): "bfile(some_file_name)".

     WARNING: The conversion between bytes and numbers in [0,1) is NOT guaranteed to yield the same results on different computers.

  * Properties:

       - prng_is_congruential is FALSE.

       - prng_can_seed is FALSE.

       - prng_can_fast_sub and prng_can_fast_con are FALSE.

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