Talk:Linear congruential generator

From Wikipedia, the free encyclopedia

You have new messages (last change).

C code example of LCG for 32-bit (or more) CPU:

const unsigned M = 0xffffffff - 8; /* 2^32 - 9 = 4294967287 = 13 * 71^2 * 65539 */
const unsigned A = 13 * 71 * 65539 + 1;
const unsigned B = 17; /* or any other relatively prime to M number */
int main() {
       unsigned c = 0;
       unsigned v = 1;
       do {
               v = ((int64_t)A * v + B) % M;
               c++;
               if (!(c & 0x3ffffff))
                        printf("%10u: %08x\n", c, v);
       } while (v != 1);
       printf("%u (0x%x) iterations: loop detected (value %08x repeats)\n", c, c, v);
       return 0;
}

Output:

  67108864: 7a15a240
 134217728: 63f193d7
...
4227858432: c3361633
4294967287 (0xfffffff7) iterations: loop detected (value 00000001 repeats)

Is it worth adding to the article?

  The Mersenne twister both runs faster than and generates higher-quality deviates than almost any LCG...

While not crypto-strong enough, LCG is fast to set up and calculate, and needs just one word of storage. For many applications this is good enough (why should I bother with creating array of 624 words for Mersenne twister if I only need a 8-byte salt for my new Unix password?). Yet the article contains only one actual example of generator (A = 1664525, B = 1013904223, M = 2^32), which is particularly bad because of that alternating even-odd sequence.

http://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html mentions some other LCGs. Is it worth adding a few of those as "good" examples too, so that people do not pick parameters which are particularly bad?

x_{n+1} = (16807 * x_n) mod (2^31 - 1) - period is 2^31-1 (right?)

x_{n+1} = (48271 * x_n) mod (2^31 - 1) - period is ???

x_{n+1} = (62089911 * x_n) mod (2^31 - 1) - period is ???

x_{n+1} = (40692 * x_n) mod (2^31 - 249) - period is ???

That page also mentions

x_n = (271828183 * x_{n-1} + 314159269 * x_{n-2}) mod (2^31 - 1)

which isn't a LCG. Is it "better" or what?

  • Gotta mention the classic Speccy one; x_{n+1} = (75 * (x_n + 1) - 1) mod (2^16 + 1) - period is 2^16.

Who ever wrote this article is obviously good at mathematics but has very poor grasp of using plain language. The grammar is extremely bad making the article baffling to anybody but the already knowledgable.

Yes, it's a lovely article kids, but for those of us on planet Earth a little more explanation might be a good idea. Or not, as you like. Greglocock 11:15, 21 September 2006 (UTC)


The following disproof is not valid:

"Choose M=11, A=5, B=1, V=1 All conditions are satisfied:-

  1)  1 and 11 are relatively prime.
  2)  11 is prime and has no prime factors.
  3)  A-1 = 4 ,  
  4)  M > max(5, 1, 1)
  5)  A > 0 , B > 0

)

Yet this yields the following sequence:- 6 9 2 0 1 6 9 2 0 1 6 "

It fails because when 11 is reduced to prime factors, the only prime factor is 11. A-1=4 is not divisible by 11, so this set of inputs fails the 2nd rule. See the article on prime factor.

Those rules can be found in the following literature: A. M. Law and W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill, New York, 1991

T. Hull and A. Dobell, Random Number Generators, SIAM Rev., 4: 230-252, 1962 ( http://locus.siam.org/SIREV/volume-04/art_1004061.html )

The text found in Hull and Dobell states that "The sequence defined by the congruence relation (1) has full period m, provided that: (i) c is relatively prime to m; (ii) a = 1 (mod p) if p is a prime factor of m; (iii) a = 1 (mod 4) if 4 is a factor of m. ", indicating that the conditions are sufficient but not necessary. (note that the formula they use is labeled as "ax + c (mod m)" ).

It seems that these rules do not work when M is prime, given what was said above in this discussion page, presumeably because of the 2nd rule. Given that, the conditions being sufficient but not necessary seems to be a popular mis-citation. I was unable to find clarifications of the rules (they are not as precice as they should be in the original paper). If there is a flaw with these rules, or if the original proof has been disproven, then many students have been taught these rules in error. Many citations in lecture notes can be found of them by searching for the literal string in www.google.com:

    "If q is a prime number that divides m, then q divides a-1"

Even if the only mis-citation is that the rules are necessary and sufficient, many students are still being taught incorrectly.

...it is not generally realised that the above generator popularised by Numerical Recipes produces alternately odd and even results!

I have generated a small sample of numbers with this algorithm in python:

x=123492981749283749834750984327
for j in range(20):
    x=(1664525*x+1013904223)%(2E32)
    print x/2E32

which has an output:

0.785777231133
0.845651109565
0.413148398268
0.837627646619
0.158487884297
0.045609648011
0.399356437255
0.773722523776
0.483888193664
0.995558579190
0.144025803070
0.549855381779
0.029355124381
0.338410701578
0.073043339593
0.464837504736
0.647570258534
0.884586895494
0.002221975800
0.534268735330

which doesn't seem to alternate odd an even results. Maybe it's a problem in my implementation, can someone clarify this?

Your code is incorrect. It should read:
x=123492981749283749834750984327
for j in range(20):
  x=(1664525*x+1013904223)%(2**32)
  print x

- 72.57.120.3 07:27, 16 July 2006 (UTC)


I reverted the removal of #'s 4 and 5 for exhibiting a full period. While they may be obvious to someone who is familiar to the problem, they may not be obvious to someone coming across LCG for the first time. Also, as far as I can tell, points 4 and 5 are not explicitly covered in points 1-3, and every time I've seen this list of 5 criteria in print, all 5 criteria are always listed. Halcyonhazard 18:18, 3 February 2007 (UTC)

Retrieved from "http://en.wikipedia.org../../../l/i/n/Talk%7ELinear_congruential_generator_c9ae.html"