0

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

Imgur

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

Imgur

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?

Atticus Stonestrom
  • 11,426
ardnew
  • 101
  • 2

2 Answers2

3

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.)

Mars
  • 1,338
2

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.

Ted
  • 33,788