One of the most important things that came out of The PCG Paper[1] is that tests are stronger as you reduce the number of state bits, and measuring this continuum is <i>much</i> more powerful than a single test. (see Figure 7)<p>It seems to me that any new non-cryptographic PRNG should be required to test itself in this manner, or else provide a very good excuse.<p>[1] <a href="http://www.pcg-random.org/paper.html" rel="nofollow">http://www.pcg-random.org/paper.html</a>
I think you’re better of reading the relevant chapter in TAOCP. It has more detail, and this doesn’t add anything from past 1970 or so. For example, it doesn’t even _mention_ the diehard and dieharder tests, let alone discuss their merits. (CORRECTION: it does. Thanks to marvy for pointing that out)<p>Also, I think the final line in this text (<i>”Correct generators usually pass tests, and buggy generators usually fail.”</i>) is at least dangerously misleading.<p>Firstly, I would use good/bad, not correct/buggy, but that is minor. My major issue is the idea that bad generators usually fail. Only really bad generators usually fail. Somewhat bad generators fail tests less often, and only slightly bad generators can pass many, many tests, only to show their weakness in some particular setting.<p>For example, if I take the output r1,r2,r3… of a good generator and swap r1 and r2 if r1>r2, r3 and r4 if r3>r4, etc. the result isn’t truly random, but will pass many tests.<p>If you suspect your generator to have this problem, it is extremely easy to test for it, but if you don’t, that may be hard.<p>A good array of tests will test subsequences, and find this easily (the average of the odd samples will typically be less than expected, and the average of the even samples will typically be larger)
This was disappointing. Not a word about correlations between subsequent numbers, period length, all the things that matter if you’re actually generating significant amounts of random numbers.
Since the discussion seems to have already degenerated into waxing poetic about this RNG or that I'd like to throw in: Do not use pseudo-random number generators. Use cryptographically secure random number generators.<p>From a performance perspective there are vanishingly few applications where the difference between MT or PCG and AES-CTR is going to make an ounce of difference. Once the question of performance is settled, there simply don't remain any arguments in favor of using PRNGs.
2/10 would not recommend for technical merit.<p>8/10 is nice if you want a handwavy human explanation of some rudimentary expectations in crypto<p>- author spends a few pages thinking about randomness - we have formal definitions of a RNG/PRNG.<p>- author does basic statistical tests, these seem very unconcerned with actual randomness - i'm not sure what the point is<p>- author really shouldn't be writing about crypto randomness if they don't do crypto<p>+1 to higher comment saying reading TAOCP instead.
This is a great read. The principles are also applicable to other problems such as evaluating a constant time comparison function, symmetrical cypher, or hash.
<p><pre><code> Software random number generators are technically
pseudorandom number generators because the output
of a deterministic program cannot really be random.
</code></pre>
On the other hand, everything we build is made of quantum particles which exhibit truly random behavior. Including the computers that run those programs. So programs cannot really be deterministic.