# Linear congruential generator

 related topics {math, number, function} {system, computer, user} {rate, high, increase} {food, make, wine} {@card@, make, design}

A Linear Congruential Generator (LCG) represents one of the oldest and best-known pseudorandom number generator algorithms.[1] The theory behind them is easy to understand, and they are easily implemented and fast.

The generator is defined by the recurrence relation:

where Xn is the sequence of pseudorandom values, and

are integer constants that specify the generator.

## Contents

### Period length

The period of a general LCG is at most m, and for some choices of a much less than that. Provided that c is nonzero, the LCG will have a full period for all seed values if and only if:[2]

While LCGs are capable of producing decent pseudorandom numbers, this is extremely sensitive to the choice of the parameters c, m, and a.

Historically, poor choices had led to ineffective implementations of LCGs. A particularly illustrative example of this is RANDU which was widely used in the early 1970s and lead to many results which are currently being questioned because of the use of this poor LCG.[3]

### Parameters in common use

The most efficient LCGs have an m equal to a power of 2, most often m = 232 or m = 264, because this allows the modulus operation to be computed by merely truncating all but the rightmost 32 or 64 bits. The following table lists the parameters of LCGs in common use, including built-in rand() functions in runtime libraries of various compilers.

[citation needed]

As shown above, LCG's do not always use all of the bits in the values they produce. The Java implementation produces 48 bits with each iteration but only returns the 32 most significant bits from these values. This is because the higher-order bits have longer periods than the lower order bits (see below). LCG's that use this technique produce much better values than those that do not.