Node:LCG, Next:QCG, Previous:ICG, Up:Definitions

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