Hacker News Reader

Comment by ifcologne | Hacker News Reader

A worth to read article by [Mike Malone](https://medium.com/@betable/tifu-by-using-math-random-f1c308...) explains the problem with Math.random() in more detail.

Quoting Donald Knuth / The Art of Computer Programming:

> “Many random number generators in use today are not very good. There is a tendency for people to avoid learning anything about such subroutines; quite often we find that some old method that is comparatively unsatisfactory has blindly been passed down from one programmer to another, and today’s users have no understanding of its limitations.”

View on HN

Possibly ironically, here was the comment above the previous implementation

https://chromium.googlesource.com/v8/v8/+/2755c5a1b1cf7fc4c5...

  //
  // This class is used to generate a stream of pseudorandom numbers. The class
  // uses a 48-bit seed, which is modified using a linear congruential formula.
  // (See Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.)

It's still not entirely clear why this particular algorithm was chosen (it'd been cool if some explanation had been given in this blog post). I suspect the reason was related to the fact that, in javascript, you can only multiply two 16 bit numbers without fear of loss of precision (without doing a fair amount of gymnastics), and they wanted something they could easily port into pure javascript to be used as a optimizer test. As partial support for that theory, the new code has now been put back almost entirely into the C++ layer.

Then again, the author might be looking at that commit and wondering "Why did we pick that algorithm?" :)

> here was the comment above the previous implementation

That's about a different RNG than the one that Mike Malone's article was about. The one you're pointing to was used on the C++ side of the world (and so doesn't have the concerns of JS numbers), the one the article was about was pure JS.

Part of the V8 update was to unify the RNGs (see the patch history), so now both use the same (better) RNG. On the JS side, the new C++ RNG is now used to fill a buffer of random numbers to amortize the cost of calling into C++ code from JS.

As for why these implementations were chosen: Mike Malone covers the commit history and probable source of the JS implementation fairly well (which is probably all you'll really get since it's been 6 years or so now). The old C++ implementation is relatively recent, with some hints to its choosing here: https://github.com/v8/v8/commit/eb381b9444c6b1ec78414d1c9375...

> you can only multiply two 16 bit numbers without fear of loss of precision (without doing a fair amount of gymnastics)

You can do signed and unsigned 32-bit integer multiplication, but there's modulo/overflow there.

You can use 26 bits integers for multiplication without fear of overflowing with IEEE 754 doubles.

That Knuth quote appears on pg. 4 of my 1969 copy of TAOCP Vol. 2. That's 46 years ago. And yet we still make these fundamental mistakes.

Fortunately, when I went to college, my first CS prof loved TAOCP, and those were probably the first three CS texts I ever owned.

I wonder if the increased length and cost has made it increasingly irrelevant. It's $175 to get a copy now.

Inaccessible rather than irrelevant. I have yet to meet an intermediate to advanced programmer who would not be improved by at least trying to get through parts of TAoCP. Sadly, I have also yet to meet more than a handful who have.

edit: sbierwagen points out below that my comment is wrong, the source was pointed out, I just missed it.

> A worth to read article by [Mike Malone](https://medium.com/@betable/tifu-by-using-math-random-f1c308...) explains the problem with Math.random() in more detail.

Probably the source of the shuffle (though it was not mentioned, its visualisation was used) considering the old implementation had been there for about 6 years (and had been partially busted until a few weeks ago)

It was mentioned.

  This has been pointed out to us, and having understood the 
  problem and after some research, we decided to reimplement 
  Math.random based on an algorithm called xorshift128+.

Hyperlink in the first sentence.

(Incidentally, the link is broken in your quote)

> Hyperlink in the first sentence.

Hah you're right, completely missed the link (I'll put up a weak defence that gray visited links in gray text didn't help).

Thank you for the correction, noted in the original comment.

> (Incidentally, the link is broken in your quote)

Unsurprising, I just copy/pasted the section without fixing up the link. Fixed.

It is the source. The link to that article is in TFA in the sentence "This has been pointed out to us...."

Thankfully, because JS's RNG is not seeded, they're free to change the algorithm.

Reply on news.ycombinator.com