16
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Relevant: en.wikipedia.org/wiki/… $\endgroup$
    – user182
    Commented Mar 4, 2012 at 17:46
  • $\begingroup$ 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. $\endgroup$
    – user182
    Commented Mar 6, 2012 at 17:31
  • 2
    $\begingroup$ 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. $\endgroup$
    – xdavidliu
    Commented Jul 23, 2018 at 17:51
  • $\begingroup$ All period lengths of LCG as functions of the parameters are calculated in Marsaglia, The Structure of Linear Congruential Sequences, Theorems 2-4. $\endgroup$
    – Conifold
    Commented Feb 1 at 14:22

1 Answer 1

Reset to default
14
$\begingroup$

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.

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:

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.

Further reading

For an excellent primer on pseudo random number generators, I would strongly recommend that you read the Numerical Recipes chapter on Random Numbers.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That is true, but I'm not constraining myself to full period LCG PRNG's... I'm curious about the poor choices of a,c, and m, such that the random streams that do not achieve full period. I'd like to be able to know ahead of time, given some a,c, and m, what will the period inevitably be. I know that it is upper bounded by m, but I was wondering if we can do better than that and obtain the exact period. $\endgroup$
    – Paul
    Commented Mar 5, 2012 at 14:34
  • $\begingroup$ I don't think this is splitting hairs on a technicality at all: the question was "how to determine the period of an LCG with arbitrary parameters", while this answer says "don't use arbitrary LCG's, always use full period LCGs, and assuming you do, the answer to your question would be the maximum possible period, by definition". The argument for using full-period LCFs laid out in this answer is perfectly convincing, but the issue is that's not at all what the question asked. $\endgroup$
    – xdavidliu
    Commented Jul 23, 2018 at 15:28
  • $\begingroup$ Sorry @xdavidliu but I don't see how your new comment helps me improve my answer. You brought to my attention that I didn't actually answer the question, I edited my answer to fix that, and then let you know in a way I thought might make you smile (if you're a Futurama fan). I don't see that anything more needs to be said. $\endgroup$
    – Mark Booth
    Commented Jul 23, 2018 at 16:09
  • $\begingroup$ Note that on stack exchange, comments are not intended for extended discussions, for that use Computational Science Chat. Comments are for helping to improve questions and answers, and are distracting, so we try to keep them to a minimum. Comments should be considered ephemeral, any comment which no longer actively helps to improve a question or answer may be deleted at any time to tidy up a post. $\endgroup$
    – Mark Booth
    Commented Jul 23, 2018 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.