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

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.

• Relevant: en.wikipedia.org/wiki/…
– user182
Commented Mar 4, 2012 at 17:46
• BTW, if you're using LFSR then the period is maximal iff the feedback polynomial is primitive. In such case, the period AFAIK (don't quote me; too lazy to dig up my course notes) is $q^n$ where the feedback polynomial $p(x) \in \mathbb{F}_{q}[x]$ of degree $n$, and $q$ is the size of the field of coefficients.
– user182
Commented Mar 6, 2012 at 17:31
• Floyd's cycle detecting algorithms as well as Brent's cycle detection algorithms are both efficient ways to detect cycles. Both will return some multiple L of the period, and once you have that, you can factorize L and see which is the smallest factor that is a period. Commented Jul 23, 2018 at 17:51
• All period lengths of LCG as functions of the parameters are calculated in Marsaglia, The Structure of Linear Congruential Sequences, Theorems 2-4. Commented Feb 1 at 14:22

If you constrain yourself to full cycle LCG PRNGs then the answer is easy, by definition it's simply $$m$$.

To find the period of a non full cycle LCG PRNG for a given seed you just need to count the number of iterations of the PRNG until it generates the seed value once more.

### 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.

# Why you want to use a full cycle generator

If you don't constrain yourself to full cycle LCG PRNGs then you are taking a huge risk.

If you don't know that a given LCG is full cycle then you could end up with a generator with an arbitrary number of mutually distinct sequences, some of which could be embarrassingly small and have appalling randomness, possibly even worse than the infamous RANDU generator.

You really don't want to have to check every possible seed value to make sure that it generates a sequence which is long enough for your application.