symbiotic / linear-congruential-generator
Linear congruential pseudo-random number generator in the range MIN - MAX
dev-master
2023-08-12 10:12 UTC
Requires
- php: >=8.0
- ext-bcmath: *
This package is auto-updated.
Last update: 2024-10-12 12:36:16 UTC
README
- For any range width from 3, it eliminates the repetition of numbers and gaps
- Generates unique numbers in the given range until the entire range is passed
- After passing the range, it produces numbers in the same order, the order of generation of numbers depends on the starting position
- Prime numbers for bias are chosen based on the passed range
Although the linear congruential method generates a statistically good pseudo-random sequence of numbers, it is not cryptographically secure. Generators based on the linear congruential method are predictable, so they cannot be used in cryptography.
Installation
composer require symbiotic/linear-congruential-generator
Usage
Important: The generator uses a cyclic range generation, so you must limit the number of iterations yourself!
use \Symbiotic\LinearCongruentialGenerator\LinearCongruentialGenerator; $LCGenerator = LinearCongruentialGenerator::create( 1, // Minimum number to generate 30, // Max number to generate 1 // Generator starting position ); // for ($i = 0; $i < 30; $i++) { echo $LCGenerator->current() . ' '; $LCGenerator->next(); } // output: 25 18 11 4 27 20 13 6 29 22 15 8 1 24 17 10 3 26 19 12 5 28 21 14 7 30 23 16 9 2
Comparison of generation with other algorithms
Algorithms for tests and comparisons are taken from the Internet and Wikipedia . They are not adapted to work within a small range, so each result for is adapted by modulo equal to the range.
General formula: X(n+1) = A*Xn + C mod M;
MMIX M = 2^64 A = 6364136223846793005 C = 1442695040888963407
Minstd M = 2^31-1 A = 16807 C = 0
BSD M = 2^31 A = 1103515245 C = 12345
Msvcrt M = 2^32 A = 214013 C = 2531011
Numbers
SymLCG
10000 - 99999 78094 93491 18888 34285 49682 65079 80476 95873 21270 36667
100000 - 999999 780794 451233 121672 692111 362550 932989 603428 273867 844306 514745
1000000 - 9999999 7807750 9346253 1884756 3423259 4961762 6500265 8038768 9577271 2115774 3654277
10000000 - 99999999 78076998 42933901 97790804 62647707 27504610 82361513 47218416 12075319 66932222 31789125
100000000 - 9999999999 7357692322 4516864389 1676036456 8735208523 5894380590 3053552657 212724724 7271896791 4431068858 1590240925
Minstd
10000 - 99999 26807 65249 50073 83658 38930 61272 57544 40878 67923 67709
100000 - 999999 116807 875249 950073 443658 308930 511272 327544 850878 877923 337709
1000000 - 9999999 1016807 4475249 3650073 4943658 2108930 3211272 3027544 9850878 1777923 1237709
10000000 - 99999999 10016807 22475249 12650073 94943658 74108930 30211272 21027544 27850878 28777923 37237709
100000000 - 9999999999 100016807 382475249 1722650073 1084943658 1244108930 570211272 201027544 1557850878 1558777923 2107237709
BSD
10000 - 99999 47590 41575 74084 52781 35474 80899 89952 86185 77886 94847
100000 - 999999 227590 401575 524084 502781 215474 800899 629952 356185 617886 634847
1000000 - 9999999 6527590 9401575 6824084 5902781 2015474 9800899 6029952 1256185 1517886 7834847
10000000 - 99999999 33527590 27401575 42824084 77902781 65015474 18800899 78029952 46256185 82517886 97834847
100000000 - 9999999999 1203527590 477401575 762824084 1247902781 2135015474 468800899 1608029952 586256185 1162517886 367834847
MMIX
10000 - 99999 16412 89417 50806 33811 16816 68205 51210 34215 85604 68609
100000 - 999999 556412 449417 590806 483811 376816 518205 411210 304215 445604 338609
1000000 - 9999999 7756412 8549417 7790806 8583811 9376816 8618205 9411210 1204215 9445604 1238609
10000000 - 99999999 25756412 62549417 79790806 26583811 63376816 80618205 27411210 64204215 81445604 28238609
100000000 - 9999999999 6235756412 4382549417 619790806 8666583811 6813376816 3050618205 1197411210 9244204215 5481445604 3628238609
Msvcrt
10000 - 99999 10041 10172 10600 11997 16559 31457 14572 24968 26149 30006
100000 - 999999 100041 100172 100600 101997 106559 121457 104572 114968 116149 120006
1000000 - 9999999 1000041 1000172 1000600 1001997 1006559 1021457 1004572 1014968 1016149 1020006
10000000 - 99999999 10000041 10000172 10000600 10001997 10006559 10021457 10004572 10014968 10016149 10020006
100000000 - 9999999999 100000041 100000172 100000600 100001997 100006559 100021457 100004572 100014968 100016149 100020006
Omissions and collisions of numbers when working in limited ranges
Generator duplicate/missed (time) SymLCG MMIX Msvcrt BSD Minstd
2 - 4 0 0 (0.099ms) 1 1 (0.037ms) 0 0 (0.022ms) 1 1 (0.020ms) 0 0 (0.030ms)
1 - 7 0 0 (0.041ms) 2 2 (0.059ms) 1 1 (0.039ms) 3 3 (0.037ms) 1 6 (0.055ms)
13 - 87 0 0 (0.385ms) 26 26 (0.571ms) 21 28 (0.313ms) 6 6 (0.410ms) 0 0 (0.536ms)
1 - 100 0 0 (0.518ms) 40 40 (0.944ms) 27 40 (0.496ms) 12 12 (0.464ms) 0 0 (0.672ms)
73 - 100 0 0 (0.150ms) 6 6 (0.211ms) 8 9 (0.109ms) 0 0 (0.128ms) 4 24 (0.191ms)
23 - 139 0 0 (0.599m 43 43 (0.908ms) 32 45 (0.436ms) 24 24 (0.511ms) 0 0 (0.860ms)
1 - 1000 0 0 (4.473ms) 472 472 (7.174ms) 126 874 (3.706ms) 53 53 (4.524ms) 0 0 (6.480ms)
457 - 1325 0 0 (3.949ms) 196 196 (6.486ms) 125 744 (3.142ms) 80 80 (4.023ms) 0 0 (5.747ms)
1 - 200000 0 0 (1.035s) 46913 145407 (1.913s) 135 199865 (760.741ms) 54366 54366 (897.711ms) 49879 49879 (1.747s)
100001 - 200000 0 0 (506.476ms) 21345 76736 (799.293ms) 135 99865 (434.825ms) 24948 24948 (717.396ms) 0 0 (726.560ms)
100001 - 300000 0 0 (1.076s) 46913 145407 (1.983s) 135 199865 (743.496ms) 54366 54366 (878.400ms) 49879 49879 (1.365s)
1304001 - 2000000 0 0 (3.579s) 16934 16934 (5.364s) 135 695865 (2.528s) 43550 43550 (3.028s) 255743 369619 (4.880s)
9223372036854675807 - 9223372036854775806 0 0 (546.518ms) 21345 76736 (762.389ms) 135 99865 (364.254ms) 24948 24948 (436.867ms) 0 0 (690.514ms)
9223372036853775807 - 9223372036854775806 0 0 (6.761s) 403515 404456 (7.858s) 135 999865 (3.628s) 114868 114868 (4.337s) 100726 100726 (7.011s)