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

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