# Does It Beat the Minimal Standard?

Suppose that you've written (or just seen someone else announce) a brand new PRNG. Cool! It's nice to have new things. But here's the question you should ask yourself; “Is it better than a reasonable ‘minimal standard’? Does it beat methods devised more than sixty years ago?”

### Wisdom from the Past

Back in 1987, more than thirty years ago now, Steve Park and Keith Miller
wrote the paper *Random Number Generators: Good Ones Are Hard to
Find*, which lamented the poor quality of many of the PRNGs in use at
the time and proposed a bare mininum for a “good enough” PRNG (the
paper appeared in CACM early the following year). In that paper, they
wrote

In retrospect it is evident that a generally satisfactory algorithm for random number generation was proposed by D. H. Lehmer 36 years ago [26]. This parametric multiplicative linear congruential algorithm has withstood the test of time. It can be implemented efficiently [27, 31, 37, 41], numerous empirical tests of the randomness of its output have been published [8, 15, 27, 28, 37], and its important theoretical properties have been analyzed [9, 14, 18, 30]. The conclusion to be drawn from all this research is now clear. Although Lehmer’s algorithm has some statistical defects, if the algorithm parameters are chosen properly and if the software implementation of the algorithm is correct, the resulting generator can produce a virtually infinite sequence of numbers that will satisfy almost any statistical test of randomness. In other words, with properly chosen parameters, Lehmer’s algorithm, correctly implemented, represents a good minimal standard generator against which all other random number generators can—and should—be judged.

Thirty years later, some specifics may have changed (i.e., the necessary parameters for what we might consider a reasonable LCG), but the fundamental idea—that any proponent of a new PRNG should be asked to explain how their technique is better than an appropriate “minimal standard” LCG—remains as relevant today is it was then.

If you can't show that your PRNG technique beats an idea from over sixty years ago, you haven't proven its worth.

### Today's 32-bit Minimal Standard: A 96-bit Truncated LCG or MCG

The code below represents a reasonable minimal-standard MCG:

```
uint96_t state = 1; // can be seeded to any odd number
uint32_t next()
{
state *= 0xdc87976860b11728995deb95;
return state >> 64;
}
```

And this version is a reasonable minimal-standard LCG:

```
uint96_t state; // can be seeded to any number
uint32_t next()
{
const uint96_t MULTIPLIER = 0xc580cadd754f7336d2eaa27d;
state *= MULTIPLIER;
state += MULTIPLIER;
// Any odd odd number will do, the multiplier is odd and
// conveniently to hand
return state >> 64;
}
```

What we know about these two PRNGs is that

- The code is incredibly simple (although it does presume the existence of a 96-bit (or larger) integer type).
- On 64-bit machines, the necessary multiplication is not difficult to perform. In fact, on modern x86 machines, the entire generation process can take place in less than a nanosecond.
- The generators are known to have long periods and no short cycles.
The LCG has period 2
^{96}, which is maximal, and no bad initializations—any initial seed is okay. The MCG provides two separate cycles of size 2^{62}and only requires that the seed be odd. - The underlying theory ensures that the generators are uniform (each output occurs the same number of times).
- Because the output function is truncation, each output occurs a
vast number of times (2
^{62}and 2^{64}, respectively), meaning that producing one output does not significantly reduce the chance of it recurring. - The underlying theory is very well understood. The multiplicative
constants were chosen to have excellent “spectral test” values (for
the MCG, normalized LLL-spectral test values are M
_{8}= 0.70279, M_{16}= 0.65345, M_{24}= 0.58118 and for the LCG, M_{8}= 0.73201, M_{16}= 0.64438, M_{24}= 0.53151, as computed by software by Karl Entacher). - The output passes stringent statistical tests, such as PractRand up to 32 TB and TestU01's BigCrush test.

In fact, not only does this 96-bit PRNG pass statistical tests, it passes
them *well*. Testing with PractRand, we can plot the failure point
for different sized 32-bit generators as follows:

This graph shows us that we leave clear-fail territory at 78 bits for
LCGs and 80 bits for MCGs. Thus a 96-bit LCG or MCG has considerable
*headroom* available to allow it to pass larger statistical tests.

Extrapolating the line from this graph shows that we'll get to the clear failure point for a 96-bit MCG at 128 petabytes of data, and for the LCG at the half exabyte point. If it takes PractRand a week of testing to test 32 TB, half an exabyte will require more than three hundred years of testing to detect statistical flaws.

### Today's 64-bit Minimal Standard: A 128-bit Truncated LCG or MCG

Similarly, if you want 64-bit output, a 128-bit truncated LCG or MCG represents a reasonable minimal standard. In fact, on 64-bit hardware, these generators are no more costly to compute that the 32-bit output versions given above.

```
uint128_t state = 1; // can be seeded to any odd number
uint64_t next()
{
state *= 0x0fc94e3bf4e9ab32866458cd56f5e605;
// Spectral test: M8 = 0.71005, M16 = 0.66094, M24 = 0.61455
return state >> 64;
}
```

```
uint128_t state; // can be seeded to any number
uint64_t next()
{
const uint128_t MULTIPLIER = 0x2d99787926d46932a4c1f32680f70c55;
state *= MULTIPLIER;
// Spectral test: M8 = 0.70420, M16 = 0.65412, M24 = 0.60209
state += MULTIPLIER;
// Any odd odd number will do, the multiplier is odd and
// conveniently to hand
return state >> 64;
}
```

Essentially the same observations we made for the 32-bit generators apply here as well. Once again, we can plot the failure point for different sized 64-bit generators as follows:

This graph shows us that we leave clear-fail territory at 109 bits for
LCGs and 111 bits for MCGs. Thus a 128-bit LCG or MCG has considerable
*headroom* available to allow it to pass larger statistical tests.

As before, we can extrapolate the line from this graph, this time finding that we reach the clear failure point for a 128-bit MCG at 256 petabytes of data, and for the LCG at the 1 exabyte point. If it takes PractRand a week of testing to test 32 TB, an exabyte will require more than six hundred years of testing to detect statistical flaws.

### Conclusion

Linear congruential generators are frequently cited as being a poor choice for random-number generation, and at small sizes that remains true, but as we have seen, at larger sizes these generators do very well in statistical tests. Forty years ago, these larger versions might have been unwieldy, but that has not been the case for a long time. Today modern 64-bit architectures have little difficulty performing 128-bit math quickly, and since 2016, even a $35 Raspberry Pi has a 64-bit quad-core CPU. And older 32-bit machines can perform 96-bit math acceptably fast—it's worth realizing that the longstanding `drand48`

generator present in all Unix systems was designed in the age of 16-bit machines and can be trivially adapted to use 32-bit data, creating `drand96`

.

Any new PRNG with 64-bit output needs to answer the question, “How is
it better than the minimal standard, a 128-bit LCG?” and likewise any PRNG with 32-bit output needs to answer the question “How is
it better than the minimal standard, a 96-bit LCG?”. It is not enough
just to be fairly fast, because these minimal standards are fast.
It is not enough to pass stringent statistical tests, because these
minimal standard generators pass those same tests, and pass them *easily*.

Moreover, the graphs we have seen show that it is possible to take a scientific approach to testing PRNGs. The trend lines we have seen allow us to make good predictions about tests that that might be prohibitively expensive to run, so we see another useful tip for designers of PRNGs. Don't just provide a single data point, provide many and do some science.

### Appendix

To allow others to recreate the above graphs, below are multiplicative constants for MCGs and LCGs of different sizes. The constants were found by using a random search to find constants that had good normalized LLL-spectral test results;
each constant is intended to be “very good” rather than truly outstanding. Each table shows the M_{8} result for the normalized LLL-spectral test. The M_{16} values are all above 0.625.

#### MCG Constants

Bits | Multiplicative Constant | Spectral Test |
---|---|---|

32 | 2739110765 | 0.716768631223 |

33 | 6416791565 | 0.741609517211 |

34 | 2110734621 | 0.730357331437 |

35 | 9409920061 | 0.727139444967 |

36 | 8124055821 | 0.726338729537 |

37 | 85397059285 | 0.745062524229 |

38 | 268237653253 | 0.742041038480 |

39 | 220322046269 | 0.729472249491 |

40 | 533248573853 | 0.741393982264 |

41 | 1159580999389 | 0.721303065856 |

42 | 4207420190797 | 0.727290948336 |

43 | 1162000279733 | 0.717554748268 |

44 | 14291355528493 | 0.721569546451 |

45 | 32316819487421 | 0.722852594721 |

46 | 27424978670797 | 0.723975492235 |

47 | 112357400097837 | 0.725660187612 |

48 | 203797216008469 | 0.728474675519 |

49 | 14838598453045 | 0.736512565883 |

50 | 406663326808437 | 0.755377478054 |

51 | 942227593642253 | 0.727499556775 |

52 | 276168391955373 | 0.738214029774 |

53 | 7207664573232381 | 0.747016695380 |

54 | 1678565460045845 | 0.727249278946 |

55 | 15485172535814365 | 0.710832966834 |

56 | 65157942103163701 | 0.729099254104 |

57 | 41826564414174485 | 0.737033978607 |

58 | 265278118812494821 | 0.720996827858 |

59 | 435341156619262861 | 0.713519610623 |

60 | 222915332783142117 | 0.737161497144 |

61 | 2042033352170702485 | 0.730916689500 |

62 | 3852213006194032149 | 0.717693049282 |

63 | 2681400331702771381 | 0.730222321935 |

64 | 14647171131086947261 | 0.738375341778 |

65 | 23586512187791901165 | 0.749719574465 |

66 | 4021396209304885645 | 0.737035361383 |

67 | 71338817522127457661 | 0.749586645884 |

68 | 23537159970439144981 | 0.741383430613 |

69 | 574409946355343590093 | 0.728499816481 |

70 | 847531188765324779717 | 0.735818093856 |

71 | 1540150647070481776589 | 0.736156422148 |

72 | 3629512676251493547269 | 0.733279877031 |

73 | 5691505500811439494453 | 0.731779832097 |

74 | 2687589216551525493141 | 0.717594710954 |

75 | 5944024556493776365117 | 0.731218718355 |

76 | 2540004110552927093773 | 0.741476230780 |

77 | 9614823434306722085205 | 0.716421804008 |

78 | 256445958763511920394925 | 0.733008689483 |

79 | 601712692362582751632037 | 0.744911691987 |

80 | 39606201209357049487589 | 0.725258169835 |

81 | 1290131957331746079373301 | 0.734219557372 |

82 | 3977675389778782791388165 | 0.756010134150 |

83 | 7621526099150505215659221 | 0.725543053961 |

84 | 9877239282961482572937501 | 0.725928715061 |

85 | 25236437150407555247393029 | 0.749180805625 |

86 | 8171031101133229061033037 | 0.740169374705 |

87 | 49362540671389698004118317 | 0.724803286548 |

88 | 2577223908231812491115693 | 0.719764670518 |

89 | 249522469266726746228387597 | 0.749826167287 |

90 | 839446671699896991292676421 | 0.727750604637 |

91 | 958856983424445520621212381 | 0.720868271564 |

92 | 936151086994606743394269365 | 0.717081973076 |

93 | 4398551187470736665765410061 | 0.737375655009 |

94 | 16575717516719574569518905037 | 0.733588588969 |

95 | 16924451041812820016938051413 | 0.738072389915 |

96 | 63684207872218969504639112949 | 0.722889364342 |

97 | 123612427885422382889677805949 | 0.720047707563 |

98 | 13564477857739332917956337261 | 0.723224899486 |

99 | 567192134585768783122181505413 | 0.727178102380 |

100 | 605302915592620321688005792373 | 0.745754947466 |

101 | 1940675479040113117551892359605 | 0.739161068408 |

102 | 3658916473478134582167183652629 | 0.753704464419 |

103 | 1571359329199485794141792737933 | 0.730697664731 |

104 | 16904445017912738760767735186589 | 0.742586816074 |

105 | 22485855570768166567205990626413 | 0.718485657687 |

106 | 74313279853458239997575461406493 | 0.720008226330 |

107 | 69789568092498811246130593789565 | 0.731015334466 |

108 | 199185148331384386512624391509277 | 0.753423145342 |

109 | 445995822870053631298584088971085 | 0.737911420945 |

110 | 522038943738820526113376981570765 | 0.728651914451 |

111 | 1790166223466728928894031445659221 | 0.745853280704 |

112 | 2376232594419346738793516431034285 | 0.739509229331 |

113 | 1739365516208071203047989829164373 | 0.752781474861 |

114 | 13159937790046761463548017391558589 | 0.735305543510 |

115 | 26771634451446385007601761491488901 | 0.724847025658 |

116 | 14592594772439033291729959800277197 | 0.744686357317 |

117 | 60966792259065248069366924264146173 | 0.741555898957 |

118 | 68836090842512112509636367404547397 | 0.746365192374 |

119 | 524186352600080584049930567274522237 | 0.739180239317 |

120 | 610775152132035755583590899855195013 | 0.747582831613 |

121 | 900387334203823311229546540549529981 | 0.745007443886 |

122 | 2306725953348125746190075336418508061 | 0.727909253640 |

123 | 1800413948600614978725384679020807301 | 0.723551474912 |

124 | 18484242130631853726820903993747978157 | 0.718440060620 |

125 | 26907765095583321268647989660234740333 | 0.722561248710 |

126 | 25076288795215231685469951584245457885 | 0.724645916794 |

127 | 34218442865726806866117399643452229733 | 0.719956739979 |

128 | 63788880824840432877499191278319602189 | 0.731606096275 |

#### LCG Constants

Bits | Multiplicative Constant | Spectral Test |
---|---|---|

32 | 1019135901 | 0.726561516888 |

33 | 6527674237 | 0.718126733013 |

34 | 15029734005 | 0.723277276010 |

35 | 3660796997 | 0.742645750618 |

36 | 29510867981 | 0.719429027076 |

37 | 63514268605 | 0.732551422652 |

38 | 116624537293 | 0.724558743348 |

39 | 194195883829 | 0.722415400434 |

40 | 568512975829 | 0.730711283118 |

41 | 1322742409629 | 0.738030287624 |

42 | 126882788757 | 0.728710926727 |

43 | 1391190336909 | 0.729854488924 |

44 | 9272727027237 | 0.722758310108 |

45 | 12790945375773 | 0.737588630205 |

46 | 15105438078773 | 0.739295363228 |

47 | 50521972618661 | 0.723112105229 |

48 | 249419361368573 | 0.730241902102 |

49 | 404273197363917 | 0.750413967945 |

50 | 178519384041629 | 0.731476180651 |

51 | 435569983484149 | 0.734296368387 |

52 | 672969485740877 | 0.748370625927 |

53 | 1997786961644461 | 0.721800591403 |

54 | 7946058339844821 | 0.741940429724 |

55 | 34210420404670109 | 0.735305419562 |

56 | 49682230424721469 | 0.751246366335 |

57 | 41552818007412365 | 0.732767196482 |

58 | 208768124490119261 | 0.720192561204 |

59 | 534186703036545445 | 0.732258727961 |

60 | 718198937956463965 | 0.717132171609 |

61 | 1492761048249620805 | 0.732951920801 |

62 | 285762664057093061 | 0.720297424345 |

63 | 5562408657945804781 | 0.740322612872 |

64 | 9199940308585234877 | 0.740159647448 |

65 | 11160153871882754749 | 0.722374537852 |

66 | 30609332369975655877 | 0.750132565315 |

67 | 102504574710574106733 | 0.727072404636 |

68 | 289008808635447097333 | 0.737066005448 |

69 | 200965074862812859469 | 0.727446643227 |

70 | 995216606425775766885 | 0.742508065267 |

71 | 1383446250119146840917 | 0.735902660153 |

72 | 1277974755392284889725 | 0.745059476563 |

73 | 755621007724937721413 | 0.723731561436 |

74 | 1403601537669505748437 | 0.735159325664 |

75 | 34430510360273607538717 | 0.739570300200 |

76 | 56021341046004321357677 | 0.732060732087 |

77 | 57428549995224081070613 | 0.737418286180 |

78 | 161279981175413397505341 | 0.736420906775 |

79 | 601009572732792860513077 | 0.744752347985 |

80 | 812978456606438465717861 | 0.725653623399 |

81 | 2230578935970333198265389 | 0.726202750322 |

82 | 3110954275176992599611333 | 0.722803877503 |

83 | 2549771676202439997119837 | 0.728988412935 |

84 | 17241119348271108561932573 | 0.733198806677 |

85 | 26457731553295723861284917 | 0.751942767791 |

86 | 59090791729463201494191589 | 0.726268118857 |

87 | 15271881663998384886817965 | 0.734997793995 |

88 | 70622416032282250170082701 | 0.730360551193 |

89 | 426541151666756081629040421 | 0.732673387845 |

90 | 1033056376707427530835730733 | 0.730196493664 |

91 | 396024176885822028546435213 | 0.730113412997 |

92 | 2388182321528562871077577165 | 0.737154295148 |

93 | 8010225565907072943071535853 | 0.728882371264 |

94 | 13261206629595072908252835605 | 0.725329755925 |

95 | 16902422804113592611251823813 | 0.750861377225 |

96 | 61124247442928732736190063229 | 0.732014535166 |

97 | 27911782745385710563574645949 | 0.734864728131 |

98 | 29938634752950390286186539269 | 0.723675443983 |

99 | 26229225708957686851411456901 | 0.735866461121 |

100 | 819029723418697416441104865757 | 0.716956721057 |

101 | 2322146411595516589823065344981 | 0.741946609263 |

102 | 1784183314298914792221437953997 | 0.730507073217 |

103 | 3235104345222420208314737169685 | 0.726129037214 |

104 | 67188141926644620722638870253 | 0.747754151762 |

105 | 2436249846286644479688629522261 | 0.723418570653 |

106 | 1825670733282477966908844273549 | 0.760448328874 |

107 | 3246539704836717185167544760429 | 0.732216405411 |

108 | 303587630294941123502336685825389 | 0.719120482824 |

109 | 11392648997474423235502837719821 | 0.751921546570 |

110 | 964268383221670159557101452712557 | 0.734010450204 |

111 | 639338642199625092864608394898789 | 0.735970283015 |

112 | 1906368178963804336466096107548453 | 0.747352401943 |

113 | 6749730758631022595149452958693405 | 0.730041084931 |

114 | 16707654375351138070845852572447229 | 0.723933957671 |

115 | 17207620364045872019394706534426421 | 0.740743821760 |

116 | 15623495417764251607984624356818501 | 0.731135297999 |

117 | 131745201739913730912678565034201349 | 0.737765053219 |

118 | 34201110710269651177692545734465877 | 0.726921739220 |

119 | 144754161049240217053622458007212997 | 0.719557456180 |

120 | 1139027868931473050531506703519921533 | 0.723535881344 |

121 | 2612106425891462620739196525511584853 | 0.734994863425 |

122 | 2009517146465439999957517982454009829 | 0.744269096369 |

123 | 8342579080939882558302521411171977885 | 0.745363344384 |

124 | 17774964191369474761588846250681198813 | 0.726741230435 |

125 | 18418224551009769296825399045980769997 | 0.724759980253 |

126 | 56967995961931505441914624497778363077 | 0.735443492446 |

127 | 92155423410782672437200603327585209317 | 0.742100869722 |

128 | 199967246047888932297834045878657099405 | 0.723283410960 |