Skip to content

Instantly share code, notes, and snippets.

@ephphatha
Last active June 22, 2021 21:30
Show Gist options
  • Save ephphatha/c7df46c2c4938f3d315c7a56434f9da2 to your computer and use it in GitHub Desktop.
Save ephphatha/c7df46c2c4938f3d315c7a56434f9da2 to your computer and use it in GitHub Desktop.
Testing LCG implementations based on the Borland constants as used in the Diablo video game
Chain looped after 4294967296 values from a total of 4294967296 candidates.
AbsDistribution yielded the following values from the given prior seed and current state:
-2147483648:
1457187811, 2147483648
-1:
0:
3604671459, 0
1:
2914375622, 4294967295
0, 1
64:
2375410851, 4294967232
538964771, 64
65:
1229260608, 65
1685115014, 4294967231
128:
1768225379, 128
1146150243, 4294967168
7625:
1480523688, 7625
1433851934, 4294959671
32458:
531810049, 4294934838
2382565573, 32458
32768:
1625910243, 32768
1288465379, 4294934528
65534:
2561524649, 65534
352850973, 4294901762
65535:
3251820486, 65535
3957522432, 4294901761
22695477:
3604671458, 4272271819
3604671460, 22695477
429496729:
1012371854, 3865470567
1902003768, 429496729
1212022642:
189776845, 1212022642
2724598777, 3082944654
2147483646:
2837779485, 2147483650
76596137, 2147483646
2147483647:
2147483648, 2147483649
766891974, 2147483647
//#include <fstream>
#include <iomanip>
#include <iostream>
#include <random>
#include <map>
// The Diablo RNG is a Linear Congruential Generator using Borland C++ constants.
// These constants result in a chain across the entire interval [0, std::numeric_limits<uint32_t>::max()]
constexpr uint32_t multiplier = 0x015A4E35; //22695477
constexpr uint32_t increment = 1; // An increment of 0 would mean that the generator can never reach 0 from a non-zero
// seed and a seed of 0 always results in a cycle of length 1 (0 -> 0)
// The modulus term is implicitly used by choosing a datatype of uint32_t and allowing the value to wrap.
constexpr auto mod = std::numeric_limits<uint32_t>::max() + 1LL; //4294967296
// The standard library defines a mod of 0 is interpreted as std::numeric_limits<T>::max() + 1 (with T being uint32_t)
// This allows us to avoid having to cast to a wider datatype to represent a value larger than the target type.
// The default constructor uses a default seed of 1. See C++ International Standard [rand.eng.lcong]
std::linear_congruential_engine<uint32_t, multiplier, increment, 0> std_rand;
// For a LCG starting with a seed of 0 results in the expression multiplier * 0 + increment, which simplifies to just increment.
// Since the Borland increment is 1, 0 always generates 1 as the next in sequence which matches the std::lcg default seed.
uint32_t seed = std_rand.default_seed;
int32_t signedSeed = std_rand.default_seed;
void AdvanceRndSeedSigned()
{
// This LCG implementation relies on implementation defined behaviour (converting an unsigned value to a signed
// value of the same bit-field width). See C++17 [conv.integral]
// In practice on two's complement systems this is treated the same as conversion from signed to unsigned, meaning
// the bit pattern is unchanged.
signedSeed = (multiplier * static_cast<uint32_t>(signedSeed)) + increment; // implied mod of std::numeric_limits<uint32_t>::max()
//return abs(signedSeed); // this is part of the distribution function
}
void AdvanceRndSeedUnsigned()
{
seed = (multiplier * seed) + increment;
//return abs(static_cast<int32_t>(seed)); // this is part of the distribution function
}
int main(int argc, char** argv) {
//std::ofstream outFile{ "numbers.txt", std::ofstream::out };
std::map<int32_t, std::vector<std::pair<uint32_t, uint32_t>>> interestingValues;
for (auto value : {
std::numeric_limits<int32_t>::min(), //undefined behaviour for abs(min), implementation defined behaviour for >>
-1, // should never be reached
0,
1,
64, // in case a distribution function special cases a power of 2
65,
128,
7625,
32458,
32768, // shift mod distribution applied to int_min is expected to yield -32678. This should be treated as a distinct value
65534, // boundary cases for shift distribution function
65535,
22695477,
429496729,
1212022642,
std::numeric_limits<int32_t>::max() - 1,
std::numeric_limits<int32_t>::max()
}) {
interestingValues.emplace(value, std::move(std::vector<std::pair<uint32_t, uint32_t>>{}));
};
uint64_t length = 0;
auto prevSeed = std_rand.default_seed;
do {
AdvanceRndSeedSigned();
AdvanceRndSeedUnsigned();
const auto randSeed = std_rand();
++length;
if (randSeed != static_cast<uint32_t>(signedSeed) || randSeed != seed) {
std::cout << "Chains diverged at length " << length
<< ", signed: " << signedSeed
<< ", unsigned: " << seed
<< ", std::random: " << randSeed << std::endl;
return 1;
}
const auto absDistMapped = abs(static_cast<int32_t>(randSeed));
if (interestingValues.contains(absDistMapped)) {
interestingValues[absDistMapped].push_back({ prevSeed, randSeed });
}
prevSeed = randSeed;
//uncomment if you have 40GB of space and about 6 hours to kill
//outFile << seed << std::endl;
} while (prevSeed != std_rand.default_seed);
std::cout << "Chain looped after " << length << " values from a total of " << mod << " candidates." << std::endl;
std::cout << "AbsDistribution yielded the following values from the given prior seed and current state:" << std::endl;
for (auto value : interestingValues) {
std::cout << value.first << ":" << std::endl;
for (auto seeds : value.second) {
std::cout << std::setw(14) << seeds.first << ", " << std::setw(10) << seeds.second << std::endl;
}
}
return 0;
}
1
22695478
2156045615
2867233980
71484141
2911408402
2613937339
1153135800
420428313
1503962414
4187371143
590113780
3101602181
234047114
1499440787
3359393392
89175345
2502193446
3898671327
3619627052
1641484573
3924779266
2060562795
471225640
3064058185
4193161758
3950339127
4130111844
1741373877
968605818
1298662723
3568402656
1287908961
3326863382
3693723791
2392223644
872325965
260785394
3588948507
3167332760
3202116729
1211716366
2887284199
1865599700
2715325925
386190954
908527603
3639521104
2499062673
1156035334
3533694015
3486216972
2154068349
1690516706
2725017291
990147080
2977565609
2956716030
1247964055
3443411012
600944149
2513793114
3876564643
2781008320
717089985
3025064438
516320239
3036490364
116626349
1061046482
2112425851
3518072
880127705
149770478
2306229575
546175412
2093058629
2910103114
869595475
2570905648
423277041
2602058982
2682279839
3775567340
1909912029
4091766978
1580452907
990666472
1141528073
2223279582
2427912951
3131105060
1039346293
1281978426
2691295235
246149792
1506147105
1394281430
1903208271
4027757916
2239337485
3336150194
1096789211
1333232472
1655898425
2692259534
2613552295
2654337172
720473765
1216007722
285309619
3466522896
66766929
4184745670
2604292863
3883174092
1350990397
3683116194
3720327563
1185291208
3375018089
360743870
2861247063
4014753284
1770501845
1320140826
2047783267
2128929664
2108955009
1583912374
3242226351
2781810748
1541973101
613761170
1374083643
1057433656
2523685785
3348315310
824480775
1663223668
2982191877
3545187850
2420411411
311216624
2869751473
4120991910
3552964191
1392593836
3670741661
1407758466
3567789803
3695814824
4289927881
3051866526
3354845623
2956492004
2112312117
31481850
2023099075
971351136
509626337
3320803222
3209547279
3492428572
3667444941
3400086642
1695979419
3076300056
2155468281
3941935758
3685028711
4266419796
981911397
2905214442
2016816499
3531502288
1212753169
1500109446
479924671
665378444
1929165565
2302528610
2055547979
3463382408
175871273
1819434878
1561471255
1448969156
1986658197
1060327386
2761421859
1462121792
2812446273
2909247862
3769678191
4246484476
4125226285
525170770
3028739323
4109361656
900946009
727083118
1902191303
313185588
312212421
2839750090
2473483987
1340861360
4186401649
578792550
215074079
4251140460
527659869
2613000258
2330902955
1133392488
1885085577
4091037022
569704567
1320376996
1919400949
1407225786
179072387
3256784416
1767036065
1820922710
1585525967
1318912220
1176253837
2092567602
4258251355
2285434584
787540665
1567553102
208716327
1463161876
2874687525
248679850
2961514547
2689414288
3231695313
2191183430
4286711935
2651212
2324118461
2678387746
1165813515
3055497032
472693225
3134290750
314009559
439484804
3040381013
18882458
3144382179
977716992
2538156801
2399919414
903299119
2057608124
127895021
824635410
2190028731
1437588408
1225428249
167171118
183234951
2531664628
2584974469
2567980426
2719117715
2904182128
2204772401
3748872230
331602911
4025513772
42996765
2636578818
1841798251
4103732264
1556440137
3826647326
1869700919
1305573476
2788451509
2083127162
3412922435
1394001888
1230872929
3567777558
667605903
3408594588
449046093
2127307762
139144475
2513211544
3302506361
1839596046
250261735
2964521428
2552625381
1999916394
1051611891
868955728
197041809
3535864326
749682495
548620812
2045115517
2424134626
1265033675
561420552
3841859241
1180555006
3157976727
2458500932
3501412629
1849044826
1397307811
1946589376
2070421441
823484662
3111388911
505954684
65099437
2615257042
3635264123
3574011256
1194459609
2033483758
4270129223
2543104180
2196204869
1282843978
1626391635
3319263024
125117681
708580326
4049351327
2053696748
2262889693
1776289730
2851256107
3006072296
3417237769
1818295518
3240885751
2773669412
3826077045
4101812026
1872229123
3633199520
222342689
3423345366
871023183
3851701340
3947878157
2996796338
3242776539
4090980952
3639596089
3512356302
64151463
1384329108
1538257317
806309162
3882993075
3367532560
140884817
3885790662
3437409791
2030657484
1675164989
226952098
3640859787
1949647560
2343551849
2497147582
2321327447
1462025476
3013237205
2687860506
1089551459
2418387584
3267316865
21243062
2756119983
661071676
2640799597
3778912146
330597691
649432888
3874076313
3469700014
2364296967
4235624052
1205306885
2906014986
3033093907
1977929968
2221433265
1083844518
3998927199
747414188
4012250525
1403670402
2888831467
2198294440
64531913
2994288798
1743051959
2365027300
917665333
1989713658
3958183363
2118445920
1136392929
1618312854
3684755727
2107167260
2323646413
972297074
2777203355
4128867352
1106749689
2118900110
1273581159
3295059284
2427857509
3273886954
2945415283
3671390672
3579123729
2666342790
1222405311
954905996
2871016957
142732130
2064750411
1377512584
1996597289
1811828350
3990660119
1069742788
2293080725
4041084634
2569240355
1516502080
470726977
2908235894
1863341167
371281148
3337730093
3271219026
3495792635
1048267000
519154521
2693240686
920772039
3981151284
2745425605
3842974922
3260819923
3640718000
956554865
2689432422
2474614815
3592132716
3189732957
3964000066
557821099
2817055080
2348987017
471774302
4099668855
2088718756
3907247861
4231909050
1965848707
2952453408
3146745761
3752075862
3081588687
3002636252
185890957
1988750130
1909124443
810737112
380616121
2855970126
2280520999
3458026260
301507365
4197518506
3687279411
635485072
3511465169
376642886
1230791551
3491187532
4068196029
3006141218
4266807819
2666026568
1303629033
3516033598
2541413079
1680111748
3131910997
4193246874
2963276259
3733032448
1981179393
588344374
3532643119
2853614268
3007334637
1121537810
3949517499
1343767224
638181401
3290235694
3173362823
3520322036
2433513349
1572947082
3999874195
1257002096
2751961905
118886182
2844440287
2262158892
3062699805
91397890
4125198187
2777785128
720172873
1326542878
928078391
732589924
2237761461
3207347834
2148932419
426774240
2205897825
3612870166
2697983631
3849559452
3217893709
169935602
584013851
1984133016
2916618873
3404116238
2560682983
2003253460
4197932005
3740781674
4040793587
2778447184
2601292177
2884522246
3072498239
3998163212
481001341
2135653090
1871006923
2120007688
4135989673
190039550
2012701079
470365764
4099470357
2502618714
472302755
1748918208
4288041665
2419060726
3347423727
3808909436
3574798765
2727937746
2174117243
3477896312
1928484057
1330622190
544717639
1372546996
1255231557
3238831178
3719335763
1734800944
2217973745
1924391654
960236959
2390442988
3677288413
2968561346
1456841259
1069657320
3881270281
823225310
1099233527
2453196068
3605753973
958656058
3244948995
2791604384
3930022177
357640662
2949176655
3033129820
996809229
3598277298
4116054747
3685437784
2653988665
2517630158
2663520935
134506132
2754761893
3140996138
3011907763
2512781072
290762321
4246652102
3136229631
2203203276
1282375741
513417890
459966347
1412983240
2553861737
2667733438
3222413399
4281414660
544275669
3696180762
2960639843
2203742592
659455873
1651749814
2259789999
11746876
3744082541
1677328018
4020645947
1876424248
3161131417
2548013742
2711095815
1425945972
1269983493
4172366858
1962025491
170973168
3628586161
552007334
2337514591
2093742508
1858410653
1082125954
2967207147
2050553512
134365385
3890128798
1672927159
3890899684
3896613173
602201594
770187459
2191012448
2124131809
2807008662
1029178383
12282140
1353403085
4250071666
1713302939
3024775960
3195632633
24545422
4212230503
129291348
2863238501
414256106
680313715
1914667216
1390742289
3888412806
3179399103
3202387084
3834102013
2195327586
2395079243
3292222344
2576071465
1381907838
3767213847
3848040900
1773487509
689753562
2186480163
4220896064
2617175105
1201452918
2295590767
2195350524
3292887853
1220294226
3528997627
628797432
4180934233
864863854
3242629319
52446004
1315946949
779035594
3639473363
1326053808
3741602161
2406435430
680622879
562556780
4094654813
1172338242
2964625323
2562162792
330122633
3644400478
782694007
2759805092
69468661
2033126842
4199580547
432743456
256916129
3675468118
3795675855
3909627612
307280781
3765291570
837425243
2480981208
628265145
1121604686
1313814567
1043890708
3898410533
3240332202
2494412339
4134027920
3195906001
2308926534
1738194559
280633932
2276737469
3721081378
2521545995
2988801352
2705252329
723999038
2317508055
3863670660
988139093
357801370
3866660067
3702543616
1281857793
761985846
2259449391
691849660
3072658413
1386196498
107775419
603236792
1611477785
4162269742
1078159239
3287650548
1305041541
3422962570
1852049299
2444385136
388566577
2081218086
3652555231
2356094252
768481821
2463251970
1126134379
519916072
3508046409
2866863902
1930777911
2142725732
3042093749
1925348730
2606966339
398284256
2870806369
1046222102
2000228751
3446682780
3541724237
562684402
1433895707
1311661720
702276985
3489357838
2033919719
3008327636
2014101221
3192867690
2091444467
509625424
4074669201
1081057286
2717513023
681506828
414515837
2704120290
1053276107
1102505736
2517779625
1864217854
2912410775
1505537348
1052940053
2058595674
1906855843
1919559360
1732806081
1100906230
2029731055
4086984572
713612461
3278136786
2829258875
3741705080
1740023769
4215201262
525235783
1061035700
2222928709
2067178314
3658766931
1844051248
1064700657
3833573862
2810177695
222403308
515963613
957695426
2497482027
3502920680
1191448329
1117117150
1103229943
1901249572
3331167093
2321493306
3319793923
1747896224
2697073697
2666150102
353040463
1303607900
633888013
2724673970
226962907
4143134808
1651866169
1587129294
2627032487
2931400084
3027810213
1509182250
2772327347
633832976
3469189457
2851410886
2506058751
4132376012
3125412669
2126594466
3572888203
3601830088
2663770473
2751549630
2074843991
3614550788
1611374549
1929182490
4171387491
1216559232
1533129345
4059513526
2558542767
565400892
3509644653
483024274
364632891
175004984
3337641113
2462304686
2670183687
1555688564
1834044421
633357066
12512531
3211845360
1454065585
109561254
3669000031
868176044
162012061
2322173314
313255915
2984156584
3157251017
3323467422
3949777591
2970706404
1117043765
2042961146
1854352323
920615264
2130665697
176004246
343088911
1234305052
3709504973
2227556722
3604551835
3790557720
2784972537
3832887182
421381223
3090615124
945877093
500337386
321785459
2287863760
1895366161
2750400390
2861245119
2844418956
3476243453
1749428578
3851840843
349141640
572116521
2408721534
1696438807
925493444
3380668565
1475316954
2418447651
716933696
3614646081
3962914422
1576766063
860322556
2648522285
546411858
3933660667
2582517496
1954173273
1415968110
1083134919
1143536180
3271533765
4116914890
119783379
2718367920
2609431665
1608849766
4228339231
3483911788
1900248157
412030274
1766687403
100280168
3076249737
2603061854
14020983
3065200548
1948787957
984894650
3390606979
4019153696
345304481
3470147670
238126543
3771450844
198246029
711305522
1848460123
2732764120
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment