Node:Table_LCG, Next:Table_ICG, Up:Tables
y_n = a * y_{n-1} + b (mod p) n > 0
Hint: A rule of thumb suggests not to use more than sqrt(p) random
numbers from an LCG.
Notice that moduli larger than 2^32 require a computer with
sizeof(long)>32.
Generators recommended by Park and Miller (1988),
"Random number generators: good ones are hard to find", Comm. ACM 31, pp. 1192-1201
(Minimal standard).
| modul p | multiplicator a
| |
| ----------- | --------------------------
| |
| 2^31 - 1 = | 2147483647 | 16807 (b = 0)
|
Generators recommended by Fishman (1990),
"Multiplicative congruential random number generators with modulus
2^beta:
An exhaustive analysis for
beta=32
and a partial analysis for
beta=48",
Math. Comp. 54, pp. 331-344.
| modul p | multiplicator a
| |
| ----------- | --------------------------
| |
| 2^31 - 1 = | 2147483647 | 950706376 (b = 0)
|
Generators recommended by L'Ecuyer (1999),
"Tables of linear congruential generators of different sizes and
good lattice structure", Math.Comp. 68, pp. 249-260.
(constant b = 0.)
Generators with short periods can be used for generating quasi-random numbers
(Quasi-Monte Carlo methods). In this case the whole period should be used.
(These figures are listed without warranty. Please see also the original paper.)
| modul p | multiplicator a
| |
| ----------- | --------------------------
| |
| 2^8 - 5 = | 251 | 33
|
| 55
| ||
|
| ||
| 2^9 - 3 = | 509 | 25
|
| 110
| ||
| 273
| ||
| 349
| ||
|
| ||
| 2^10 - 3 = | 1021 | 65
|
| 331
| ||
|
| ||
| 2^11 - 9 = | 2039 | 995
|
| 328
| ||
| 393
| ||
|
| ||
| 2^12 - 3 = | 4093 | 209
|
| 235
| ||
| 219
| ||
| 3551
| ||
|
| ||
| 2^13 - 1 = | 8191 | 884
|
| 1716
| ||
| 2685
| ||
|
| ||
| 2^14 - 3 = | 16381 | 572
|
| 3007
| ||
| 665
| ||
| 12957
| ||
|
| ||
| 2^15 - 19 = | 32749 | 219
|
| 1944
| ||
| 9515
| ||
| 22661
| ||
|
| ||
| 2^16 - 15 = | 65521 | 17364
|
| 33285
| ||
| 2469
| ||
|
| ||
| 2^17 - 1 = | 131071 | 43165
|
| 29223
| ||
| 29803
| ||
|
| ||
| 2^18 - 5 = | 262139 | 92717
|
| 21876
| ||
|
| ||
| 2^19 - 1 = | 524287 | 283741
|
| 37698
| ||
| 155411
| ||
|
| ||
| 2^20 - 3 = | 1048573 | 380985
|
| 604211
| ||
| 100768
| ||
| 947805
| ||
| 22202
| ||
| 1026371
| ||
|
| ||
| 2^21 - 9 = | 2097143 | 360889
|
| 1043187
| ||
| 1939807
| ||
|
| ||
| 2^22 - 3 = | 4194301 | 914334
|
| 2788150
| ||
| 1731287
| ||
| 2463014
| ||
|
| ||
| 2^23 - 15 = | 8388593 | 653276
|
| 3219358
| ||
| 1706325
| ||
| 6682268
| ||
| 422527
| ||
| 7966066
| ||
|
| ||
| 2^24 - 3 = | 16777213 | 6423135
|
| 7050296
| ||
| 4408741
| ||
| 12368472
| ||
| 931724
| ||
| 15845489
| ||
|
| ||
| 2^25 - 39 = | 33554393 | 25907312
|
| 12836191
| ||
| 28133808
| ||
| 25612572
| ||
| 31693768
| ||
|
| ||
| 2^26 - 5 = | 67108859 | 26590841
|
| 19552116
| ||
| 66117721
| ||
|
| ||
| 2^27 - 39 = | 134217689 | 45576512
|
| 63826429
| ||
| 3162696
| ||
|
| ||
| 2^28 - 57 = | 268435399 | 246049789
|
| 140853223
| ||
| 29908911
| ||
| 104122896
| ||
|
| ||
| 2^29 - 3 = | 536870909 | 520332806
|
| 530877178
| ||
|
| ||
| 2^30 - 35 = | 1073741789 | 771645345
|
| 295397169
| ||
| 921746065
| ||
|
| ||
| 2^31 - 1 = | 2147483647 | 1583458089
|
| 784588716
| ||
|
| ||
| 2^32 - 5 = | 4294967291 | 1588635695
|
| 1223106847
| ||
| 279470273
| ||
|
| ||
| 2^33 - 9 = | 8589934583 | 7425194315
|
| 2278442619
| ||
| 7312638624
| ||
|
| ||
| 2^34 - 41 = | 17179869143 | 5295517759
|
| 473186378
| ||
|
| ||
| 2^35 - 31 = | 34359738337 | 3124199165
|
| 22277574834
| ||
| 8094871968
| ||
|
| ||
| 2^36 - 5 = | 68719476731 | 49865143810
|
| 45453986995
| ||
|
| ||
| 2^37 - 25 = | 137438953447 | 76886758244
|
| 2996735870
| ||
| 85876534675
| ||
|
| ||
| 2^38 - 45 = | 274877906899 | 17838542566
|
| 101262352583
| ||
| 24271817484
| ||
|
| ||
| 2^39 - 7 = | 549755813881 | 61992693052
|
| 486583348513
| ||
| 541240737696
| ||
|
| ||
| 2^40 - 87 = | 1099511627689 | 1038914804222
|
| 88718554611
| ||
| 937333352873
| ||
|
| ||
| 2^41 - 21 = | 2199023255531 | 140245111714
|
| 416480024109
| ||
| 1319743354064
| ||
|
| ||
| 2^42 - 11 = | 4398046511093 | 2214813540776
|
| 2928603677866
| ||
| 92644101553
| ||
|
| ||
| 2^43 - 57 = | 8796093022151 | 4928052325348
|
| 4204926164974
| ||
| 3663455557440
| ||
|
| ||
| 2^44 - 17 = | 17592186044399 | 6307617245999
|
| 11394954323348
| ||
| 949305806524
| ||
|
| ||
| 2^45 - 55 = | 35184372088777 | 25933916233908
|
| 18586042069168
| ||
| 20827157855185
| ||
|
| ||
| 2^46 - 21 = | 70368744177643 | 63975993200055
|
| 15721062042478
| ||
| 31895852118078
| ||
|
| ||
| 2^47 - 115 = | 140737488355213 | 72624924005429
|
| 47912952719020
| ||
| 106090059835221
| ||
|
| ||
| 2^48 - 59 = | 281474976710597 | 49235258628958
|
| 51699608632694
| ||
| 59279420901007
| ||
|
| ||
| 2^49 - 81 = | 562949953421231 | 265609885904224
|
| 480567615612976
| ||
| 305898857643681
| ||
|
| ||
| 2^50 - 27 = | 1125899906842597 | 1087141320185010
|
| 157252724901243
| ||
| 791038363307311
| ||
|
| ||
| 2^51 - 129 = | 2251799813685119 | 349044191547257
|
| 277678575478219
| ||
| 486848186921772
| ||
|
| ||
| 2^52 - 47 = | 4503599627370449 | 4359287924442956
|
| 3622689089018661
| ||
| 711667642880185
| ||
|
| ||
| 2^53 - 111 = | 9007199254740881 | 2082839274626558
|
| 4179081713689027
| ||
| 5667072534355537
| ||
|
| ||
| 2^54 - 33 = | 18014398509481951 | 9131148267933071
|
| 3819217137918427
| ||
| 11676603717543485
| ||
|
| ||
| 2^55 - 55 = | 36028797018963913 | 33266544676670489
|
| 19708881949174686
| ||
| 32075972421209701
| ||
|
| ||
| 2^56 - 5 = | 72057594037927931 | 4595551687825993
|
| 26093644409268278
| ||
| 4595551687828611
| ||
|
| ||
| 2^57 - 13 = | 144115188075855859 | 75953708294752990
|
| 95424006161758065
| ||
| 133686472073660397
| ||
|
| ||
| 2^58 - 27 = | 288230376151711717 | 101565695086122187
|
| 163847936876980536
| ||
| 206638310974457555
| ||
|
| ||
| 2^59 - 55 = | 576460752303423433 | 346764851511064641
|
| 124795884580648576
| ||
| 573223409952553925
| ||
|
| ||
| 2^60 - 93 = | 1152921504606846883 | 561860773102413563
|
| 439138238526007932
| ||
| 734022639675925522
| ||
|
| ||
| 2^61 - 1 = | 2305843009213693951 | 1351750484049952003
|
| 1070922063159934167
| ||
| 1267205010812451270
| ||
|
| ||
| 2^62 - 57 = | 4611686018427387847 | 2774243619903564593
|
| 431334713195186118
| ||
| 2192641879660214934
| ||
|
| ||
| 2^63 - 25 = | 9223372036854775783 | 4645906587823291368
|
| 2551091334535185398
| ||
| 4373305567859904186
| ||
|
| ||
| 2^64 - 59 = | 18446744073709551557 | 13891176665706064842
|
| 2227057010910366687
| ||
| 18263440312458789471
|