The v8 Math.random() code was changed yesterday[0], maybe in response to this. However, the update appears to be misguided[1]...
0. https://github.com/v8/v8/commit/623cbdc5432713badc9fe1d605c5...
0. https://github.com/v8/v8/commit/623cbdc5432713badc9fe1d605c5...
Full commit message: "Tweak RNG." Reviewer comment: "LGTM" landed
No reason for the change, no source code comment, no discussion?
This specific RNG follows a traditional approach (that is, like in C or Java standard libraries) to have one algorithm in the standard library that is "as fast as possible, as bad as possible." Which meant even "just multiply with constant, add another constant, return. Bad? Yes we know." So it's still on the level "it's two multiplies and two-three adds."
Traditionally, those who expect some specific properties, like the author of the article, should have actually used the implementation they added to their code (for example MT if it fits) if they ultimately cared about the speed and wanted exactly the properties they know they needed, or if they just didn't care about the speed used some much "slower" but "much better" library.
Maybe the tradition can be broken in this specific case, I really don't know which benchmarks define what's acceptable here. Note also that the implementation must be verified, just the fact that there is somewhere some implementation available doesn't even mean that it does what is expected to do. The devil is in the details here.
* The state size is 2kb
* It fails some rudimentary statistical tests
* The output is trivially predicted
* It isn't particularly fast
* It lacks multi-stream support
If you need a CSPRNG use ChaCha20 or AES. For simulation use PCG.
contains a nice comparison table.
Wikipedia entry for MT specifies some of the problems.
PRNG design is an empirical science. We can implement a generator and throw it into a statistical battery. If one passes, we've got a constructive proof of goodness. Any of us can run BigCrush and verify the results. Unlike CSPRNGs, we don't need to sit around and wait for the results of cryptanalysis.
Comparing to ChaCha20, which is a CSPRNG, is a little apples/oranges.
But I know that MT is a very good algorithm and using it has a certain pragmatic appeal - you make a lot of people's lives easier because when they Google to learn more about your generator they'll find good information quickly.
MT is far from a "bad generator". It doesn't pass a few stringent TestU01 tests, which is the case for a number of very well regarded generators.
Simple PCG PRNGs are fast and pass TestU01 BigCrush. Someone could conceivably cook up a new battery of tests that it fails on, but we'd need to reevaluate the whole zoology of RNGs at this point.
Edit: Sorry, I was playing loose classifying MT's BigCrush failures as rudimentary. That said, I think failing any part of BigCrush should disqualify a PRNG from use.
Would include the PCG family then?
When it comes down to it, PRNG quality gets assessed empirically. Why would you use ever a generator with 2kb of state when faster & smaller generators like PCG or Xorshift* pass the same statistical battery?
You can also write proofs about their behavior to ferret out the lousy ones. For example, we can demonstrate that PCG is full period. Consider the inner LCG:
x1 = (ax0 + c) % m
If you look at the permutation function, it's also provably unbiased by counting. Since all possible bit sequences are fairly represented in the PCG state we know that all combinations of permuting bits appear with all possible output bits.