Slashdot Mirror
Fixing JavaScript's Broken Random Number Generator (hackaday.com)
szczys writes: It is surprising to learn how broken the JavaScript Random Number Generator has been for the past six years. The problem is compounded by the fact that Node.js uses the same broken Math.random() module. Learning about why this is broken is interesting, but perhaps even more interesting is how the bad code got there in the first place. It seems that a forum thread from way back in 1999 shared two versions of the code. If you read to the end of the thread you got the working version, if you didn't make it that far (perhaps the case with JavaScript devs) you got the bad version of the code whose fix is just now being rolled out.
https://xkcd.com/221/
1% APY, No fees, Online Bank https://captl1.co/2uIErYq Don't let your $$$ sit in a no-interest acct.
Blame slashdot. TFA's made it pretty clear it's the V8 engine that had been broken for six years.
The article doesn't claim it's new information. The article is about the fact that Google has finally fixed it and the backstory behind the broken code.
I've seen some pretty bad "random number" generators in my time. In one case, it was implemented by a pointer that would walk through the processes memory space and use whatever it found as-is. And another where the coder clearly thought that if you multiply something by enough made up crap and take the remainder, you get randomness. An understanding of random numbers in computing is not something the classrooms ever cover as far as I can tell.
See this table for support: http://caniuse.com/#feat=getra...
It's great that they're finally improving Math.random(), but node.js should've had crypto.getRandomValues() from the start.
TFA isn't that good either though. It spends the first half of the page with patronising pedantry about how numbers cannot be random, which is a waste of time since ‘random’ can mean ‘randomly chosen’. Here, I'll have a go at summarising the situation.
V8's random number generator is pretty bad. It's a thing called MWC1616, which basically means it's two multiply with carry random number generators, of whose outputs the lower 16-bits are concatenated to form a single 32-bit number. MWC generators aren't particularly good; they're related to linear congruential generators. But sticking two together could improve the cycle length, as long as the cycles are different. But due to the fact that MWC1616 sticks two 16-bits numbers together, the most significant bits just have the short cycle length. That's a problem, because in many random number applications the most significant bits tend to be more... eh... significant. Examples include the use of multiply-and-floor to roll dice (d = floor(rnd * 6)) or when the number gets used straight-up in physical simulations. So the effective cycle of MWC1616 is pretty short.
There's an interesting lesson here, by the way, as the original author of the algorithm could have known about this problem if he had thought his method of combining the generators through, but ‘the algorithm passed all tests’ so it was good. I too often see code that passes unit-tests but that's nevertheless deeply flawed, so please, people, if you've only got time to either write unit tests or think, then please, please think - it's more important. Later, the author did think about it, and did realise his mistake and published a different version, but the original got published in various places, including on Wikipedia. And hey, it's on Wikipedia, and it has a cited source, so it must be good, right?
The fact that MWC1616 was an odd choice was picked up during code review. The reviewer noted the odd choice saying ‘I would have gone with mersenne twister’ but the algorithm wasn't changed or investigated. The warning was raised, but not acted upon. Another important lesson: if you have code review, use the results, otherwise it's pointless busywork.
So, did the V8 random number generator get replaced by the Mersenne twister? No, they opted to use XorShift128+, presumably because it's slightly faster and uses a lot less memory, while still passing common randomness tests. But I have my reservations about this decision. The Mersenne twister is fast enough, well-understood, hard to misuse and has a long cycle-length. XorShift is by the same author as MWC1616 and relatively unknown, so there's (in my view) a bigger chance that it contains some bigger as-yet undiscovered hidden flaw.