How can I determine the period of my pseudo-random number generator?

Question

Suppose I'm using a linear congruential pseudo-random number generator (PRNG). Given a seed $x_0$, the multiplying factor (a), the shift factor (c) and the modulus factor (m), how can I determine the period of my PRNG? Do I determine it by experimentation / pattern detection algorithms, or is there a direct formula for calculating its period?

Although my question is specifically about the linear congruential method, I am open to knowing more about how periods are calculated in practice for other PRNG's as well.

Answer 1

As J.D. suggests, if you constrain yourself to full cycle LCG PRNGs then the answer is easy, by definition it's simply $m$.

From the referenced wikipedia page:

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:

• $c$ and $m$ are relatively prime,
• $a - 1$ is divisible by all prime factors of $m$
• $a - 1$ is a multiple of 4 if $m$ is a multiple of 4.

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.