Linear Congruential Generator - Period Length

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:

  1. and are relatively prime,
  2. is divisible by all prime factors of ,
  3. is a multiple of 4 if is a multiple of 4.

These three requirements are referred to as the Hull-Dobell Theorem. 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 led to many results which are currently being questioned because of the use of this poor LCG.

Read more about this topic:  Linear Congruential Generator

Famous quotes containing the words period and/or length:

    Words convey the mental treasures of one period to the generations that follow; and laden with this, their precious freight, they sail safely across gulfs of time in which empires have suffered shipwreck and the languages of common life have sunk into oblivion.
    —Anonymous. Quoted in Richard Chevenix Trench, On the Study of Words, lecture 1 (1858)

    those far-fet helps be such
    As do bewray a want of inward touch,
    and sure at length stolen goods do come to light.
    But if, both for your love and skill, your name
    You seek to nurse at fullest breasts of Fame,
    Stella behold, and then begin to indite.
    Sir Philip Sidney (1554–1586)