Editing Linear congruential generator (section)

=== ''m'' a power of 2, ''c'' ≠ 0 ===
When ''c'' ≠ 0, correctly chosen parameters allow a period equal to ''m'', for all seed values. This will occur [[if and only if]]:{{r|KnuthV2|p=17–19}}
# <math>m</math> and <math>c</math> are coprime,
# <math>a - 1</math> is divisible by all [[prime factor]]s of <math>m</math>,
# <math>a - 1</math> is divisible by 4 if <math>m</math> is divisible by 4.

These three requirements are referred to as the Hull–Dobell Theorem.<ref>{{Cite journal
 |last1=Hull |first1=T. E. |last2=Dobell |first2=A. R.
 |date=July 1962
 |title=Random Number Generators
 |url=http://chagall.med.cornell.edu/BioinfoCourse/PDFs/Lecture4/random_number_generator.pdf
 |journal=SIAM Review |volume=4 |issue=3 |pages=230–254 
 |access-date=2016-06-26 |doi=10.1137/1004061
|bibcode=1962SIAMR...4..230H |hdl=1828/3142 |hdl-access=free }}</ref><ref name="HullDobell">{{cite book
 |title=System Modeling and Simulation
 |publisher=John Wiley & Sons, Ltd.
 |last=Severance |first=Frank |year=2001 |page=86
 |isbn=978-0-471-49694-6
}}</ref>

This form may be used with any ''m'', but only works well for ''m'' with many repeated prime factors, such as a power of 2; using a computer's [[word size]] is the most common choice.  If ''m'' were a [[square-free integer]], this would only allow ''a''&nbsp;≡&nbsp;1 (mod&nbsp;''m''), which makes a very poor PRNG; a selection of possible full-period multipliers is only available when ''m'' has repeated prime factors.

Although the Hull–Dobell theorem provides maximum period, it is not sufficient to guarantee a ''good'' generator.{{r|Park88|p=1199}}  For example, it is desirable for ''a''&nbsp;−&nbsp;1 to not be any more divisible by prime factors of ''m'' than necessary.  If ''m'' is a power of 2, then ''a''&nbsp;−&nbsp;1 should be divisible by 4 but not divisible by 8, i.e.&nbsp;''a''&nbsp;≡&nbsp;5&nbsp;(mod&nbsp;8).{{r|KnuthV2|at=§3.2.1.3}}

Indeed, most multipliers produce a sequence which fails one test for non-randomness or another, and finding a multiplier which is satisfactory to all applicable criteria{{r|KnuthV2|at=§3.3.3}} is quite challenging.{{r|Park88}}  The [[spectral test]] is one of the most important tests.<ref name=Austin2008>{{cite web |first=David |last=Austin |title=Random Numbers: Nothing Left to Chance |date=March 2008 |publisher=American Mathematical Society |work=Feature Column |url=https://www.ams.org/publicoutreach/feature-column/fcarc-random}}</ref>

Note that a power-of-2 modulus shares the problem as described above for ''c''&nbsp;=&nbsp;0: the low ''k'' bits form a generator with modulus 2<sup>''k''</sup> and thus repeat with a period of 2<sup>''k''</sup>; only the most significant bit achieves the full period.  If a pseudorandom number less than ''r'' is desired, {{floor|''rX''/''m''}} is a much higher-quality result than ''X'' mod ''r''.  Unfortunately, most programming languages make the latter much easier to write (<code>X % r</code>), so it is very commonly used.

The generator is ''not'' sensitive to the choice of ''c'', as long as it is relatively prime to the modulus (e.g. if ''m'' is a power of 2, then ''c'' must be odd), so the value ''c''=1 is commonly chosen.

The sequence produced by other choices of ''c'' can be written as a simple function of the sequence when ''c''=1.{{r|KnuthV2|p=11}}  Specifically, if ''Y'' is the prototypical sequence defined by ''Y''<sub>0</sub> =&nbsp;0 and ''Y''<sub>''n''+1</sub> =&nbsp;''aY<sub>n</sub>''&nbsp;+&nbsp;1 mod&nbsp;m, then a general sequence ''X''<sub>''n''+1</sub> =&nbsp;''aX<sub>n</sub>''&nbsp;+&nbsp;''c'' mod&nbsp;''m'' can be written as an affine function of ''Y'':
:<math>X_n = (X_0(a-1)+c)Y_n + X_0 = (X_1 - X_0)Y_n + X_0 \pmod m.</math>
More generally, any two sequences ''X'' and ''Z'' with the same multiplier and modulus are related by
:<math>{ X_n - X_0 \over X_1 - X_0 } = Y_n = {a^n - 1 \over a - 1} = { Z_n - Z_0 \over Z_1 - Z_0 } \pmod m.</math>

In the common case where ''m'' is a power of 2 and ''a''&nbsp;≡&nbsp;5&nbsp;(mod&nbsp;8) (a desirable property for other reasons), it is always possible to find an initial value ''X''<sub>0</sub> so that the denominator ''X''<sub>1</sub>&nbsp;−&nbsp;''X''<sub>0</sub> ≡&nbsp;±1&nbsp;(mod&nbsp;''m''), producing an even simpler relationship.  With this choice of ''X''<sub>0</sub>, ''X<sub>n</sub>'' =&nbsp;''X''<sub>0</sub>&nbsp;±&nbsp;''Y<sub>n</sub>'' will remain true for all ''n''.{{r|Steele20|p=10-11}} The sign is determined by ''c''&nbsp;≡&nbsp;±1&nbsp;(mod&nbsp;4), and the constant ''X''<sub>0</sub> is determined by 1&nbsp;∓&nbsp;''c''&nbsp;≡&nbsp;(1&nbsp;−&nbsp;''a'')''X''<sub>0</sub>&nbsp;(mod&nbsp;''m'').<!--1∓c is a multiple of 4, and 1−a ≡ 4 (mod 8), so this has solutions mod m/4-->

As a simple example, consider the generators ''X''<sub>''n''+1</sub> =&nbsp;157''X<sub>n</sub>''&nbsp;+&nbsp;3 mod&nbsp;256 and ''Y''<sub>''n''+1</sub> =&nbsp;157''Y<sub>n</sub>''&nbsp;+&nbsp;1 mod&nbsp;256; i.e. ''m''&nbsp;=&nbsp;256, ''a''&nbsp;=&nbsp;157, and ''c''&nbsp;=&nbsp;3.  Because 3&nbsp;≡&nbsp;−1&nbsp;(mod&nbsp;4), we are searching for a solution to 1&nbsp;+&nbsp;3&nbsp;≡&nbsp;(1&nbsp;−&nbsp;157)''X''<sub>0</sub>&nbsp;(mod&nbsp;256).  This is satisfied by ''X''<sub>0</sub>&nbsp;≡&nbsp;41&nbsp;(mod&nbsp;64), so if we start with that, then ''X<sub>n</sub>'' ≡&nbsp;''X''<sub>0</sub>&nbsp;−&nbsp;''Y<sub>n</sub>''&nbsp;(mod&nbsp;256) for all ''n''.

For example, using ''X''<sub>0</sub> = 233 = 3&times;64 + 41:
* ''X'' = 233, 232, 75, 2, 61, 108, ...<!--63, 166, 209, 48, 115, 138, 165, 52, 231-->
* ''Y'' = 0, 1, 158, 231, 172, 125, ...<!--170, 67, 24, 185, 118, 95, 68, 181, 2-->
* ''X''&nbsp;+&nbsp;''Y'' mod 256 = 233, 233, 233, 233, 233, 233, ...