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

- 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