# Do all LCG-based PRNGs suffer from predictable patterns?

I needed to produce trivial (low-quality) random integers and remembered how simple linear congruential generators were to implement from school:

Went to Wikipedia, found the first example which appeared to produce 32 bits (sourced from the ubiquitous Numerical Recipes):

Jammed this in as the following Perl one-liner, which takes the 10th iteration (n = 10) and the current Unix time as seed:

perl -le '$n = shift; for (1..10) {$n = int(1664525 * $n + 1013904223) % 2**32 } print$n' $(date +%s)  And I was a little surprised to see the last digit in the output was always incrementing by 1. So I printed all of the iterates to find that this pattern occurs only in the 10th iteration: ~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }'$(date +%s)
seed = 1603820918
1 = 3975067229
2 = 810304536
3 = 3116890263
4 = 2673982730
5 = 3148974305
6 = 3740634316
7 = 619471291
8 = 3601034206
9 = 3361989029
10 = 1048979136     # <-  6

~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }' $(date +%s) seed = 1603820919 1 = 3976731754 2 = 1199874241 3 = 1762722604 4 = 2832966811 5 = 1716457790 6 = 2657060741 7 = 2470761248 8 = 3240913919 9 = 1251936594 10 = 1295718537 # <- 7 ~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }'$(date +%s)
seed = 1603820920
1 = 3978396279
2 = 1589443946
3 = 408554945
4 = 2991950892
5 = 283941275
6 = 1573487166
7 = 27083909
8 = 2880793632
9 = 3436851455
10 = 1542457938     # <-  8

~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }' $(date +%s) seed = 1603820921 1 = 3980060804 2 = 1979013651 3 = 3349354582 4 = 3150934973 5 = 3146392056 6 = 489913591 7 = 1878373866 8 = 2520673345 9 = 1326799020 10 = 1789197339 # <- 9 ~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }'$(date +%s)
seed = 1603820922
1 = 3981725329
2 = 2368583356
3 = 1995186923
4 = 3309919054
5 = 1713875541
6 = 3701307312
7 = 3729663823
8 = 2160553058
9 = 3511713881
10 = 2035936740     # <-  0

~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }' $(date +%s) seed = 1603820923 1 = 3983389854 2 = 2758153061 3 = 641019264 4 = 3468903135 5 = 281359026 6 = 2617733737 7 = 1285986484 8 = 1800432771 9 = 1401661446 10 = 2282676141 # <- 1 ~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }'$(date +%s)
seed = 1603820924
1 = 3985054379
2 = 3147722766
3 = 3581818901
4 = 3627887216
5 = 3143809807
6 = 1534160162
7 = 3137276441
8 = 1440312484
9 = 3586576307
10 = 2529415542     # <-  2

~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }' $(date +%s) seed = 1603820925 1 = 3986718904 2 = 3537292471 3 = 2227651242 4 = 3786871297 5 = 1711293292 6 = 450586587 7 = 693599102 8 = 1080192197 9 = 1476523872 10 = 2776154943 # <- 3 ~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }'$(date +%s)
seed = 1603820926
1 = 3988383429
2 = 3926862176
3 = 873483583
4 = 3945855378
5 = 278776777
6 = 3661980308
7 = 2544889059
8 = 720071910
9 = 3661438733
10 = 3022894344     # <-  4

~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }' $(date +%s) seed = 1603820927 1 = 3990047954 2 = 21464585 3 = 3814283220 4 = 4104839459 5 = 3141227558 6 = 2578406733 7 = 101211720 8 = 359951623 9 = 1551386298 10 = 3269633745 # <- 5 ~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }'$(date +%s)
seed = 1603820928
1 = 3991712479
2 = 411034290
3 = 2460115561
4 = 4263823540
5 = 1708711043
6 = 1494833158
7 = 1952501677
8 = 4294798632
9 = 3736301159
10 = 3516373146     # <-  6

~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }' $(date +%s) seed = 1603820929 1 = 3993377004 2 = 800603995 3 = 1105947902 4 = 127840325 5 = 276194528 6 = 411259583 7 = 3803791634 8 = 3934678345 9 = 1626248724 10 = 3763112547 # <- 7 ~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }'$(date +%s)
seed = 1603820930
1 = 3995041529
2 = 1190173700
3 = 4046747539
4 = 286824406
5 = 3138645309
6 = 3622653304
7 = 1360114295
8 = 3574558058
9 = 3811163585
10 = 4009851948     # <-  8

~ perl -le '$$n = shift; print "seed =$$n"; for (1..10) { $$n = int(1664525 *$$n + 1013904223) % 2**32; printf "%2d = %d\n", $$_,$$n }' \$(date +%s)
seed = 1603820931
1 = 3996706054
2 = 1579743405
3 = 2692579880
4 = 445808487
5 = 1706128794
6 = 2539079729
7 = 3211404252
8 = 3214437771
9 = 1701111150
10 = 4256591349     # <-  9


So I'm curious if this is a quirk of the programming? Of the chosen a, c, and m parameters? Or do all LCGs suffer from these low-period patterns?

It's not uncommon for there to be patterns in the low bits of PRNG outputs. And as you realize, LCGs are not state of the art.

For insight on this issue, a good starting point is Melissa O'Neill's paper. She has an extended discussion of problems with low bits in LCGs and other PRNGs. The PRNGs she develops are based on LCGs, but involve rearranging their outputs to try to avoid such problems.

Some of the papers or web pages at Sebastiano Vigna's website are also relevant to issues with low bits. And if that's not enough to satisfy your curiosity, Pierre L'Ecuyer's website is a great resource. (His paper with Pannetton and Matsumoto (available at L'Ecuyer's site) shows that even mathematically sophisticated PRNGs can have problems when the seed has too many zero bits. Vigna's paper about retiring the Mersenne Twister algorithm is relevant to this issue, too.)

(And one has to mention Knuth's The Art of Computer Programming, volume 2, chapter 3. People call this the bible of pseudorandom number generation, and it deserves that title even though it's no longer enough. It is still the bible for LCGs, though, and worthy of study in any event.)

You are comparing the same iteration number from different seeds, which is not the typical use of a random number generator. Usually you fix a seed and take some number of iterations.

There are patterns in other iteration numbers too; for example, if you look at iteration 1 from all your seeds, the last digit alternates between 4 and 9.

Whether this pattern is a problem depends on your application, because it arises from a nonstandard use of the random number generator. If you are generating a statistical sample of a data set, for example, it is probably no big deal, because you will not be using multiple seeds anyway (or if you do, they will be separated by a random amount of time). If used in an adversarial context where someone might be trying to reverse-engineer your random numbers (e.g., cryptographic purposes), it might cause a problem.