4 ms·

A worth to read article by [Mike Malone](https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.a7ewychse https://medium.com/@betable/tifu-by-using

A worth to read article by [Mike Malone](https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.a7ewychse 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.”

PhantomGremlin 11y ago
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.
- smackfu 11y ago
  I wonder if the increased length and cost has made it increasingly irrelevant. It's $175 to get a copy now.
  - jeremysmyth 11y ago
    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.
masklinn 11y ago
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-f1c308c4fd9d#.a7ewychse 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)
- sbierwagen 11y 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)
  - masklinn 11y ago
    > 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.
- devrelm 11y ago
  It is the source. The link to that article is in TFA in the sentence "This has been pointed out to us...."
archgoon 11y ago
Possibly ironically, here was the comment above the previous implementation https://chromium.googlesource.com/v8/v8/+/2755c5a1b1cf7fc4c5c614378e5231636e6dcff5%5E%21/#F1 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?" :)
- magicalist 11y ago
  > 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/eb381b9444c6b1ec78414d1c9375f67c320cae74 https://github.com/v8/v8/commit/eb381b9444c6b1ec78414d1c9375...
- deleted 11y ago
  [deleted]
- TazeTSchnitzel 11y ago
  > 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.
TazeTSchnitzel 11y ago
Thankfully, because JS's RNG is not seeded, they're free to change the algorithm.

PhantomGremlin 11y ago

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.

smackfu 11y ago
I wonder if the increased length and cost has made it increasingly irrelevant. It's $175 to get a copy now.
- jeremysmyth 11y ago
  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.

masklinn 11y ago

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-f1c308c4fd9d#.a7ewychse 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)

sbierwagen 11y 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)
- masklinn 11y ago
  > 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.
devrelm 11y ago
It is the source. The link to that article is in TFA in the sentence "This has been pointed out to us...."

archgoon 11y ago

Possibly ironically, here was the comment above the previous implementation https://chromium.googlesource.com/v8/v8/+/2755c5a1b1cf7fc4c5c614378e5231636e6dcff5%5E%21/#F1 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?" :)

magicalist 11y ago
> 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/eb381b9444c6b1ec78414d1c9375f67c320cae74 https://github.com/v8/v8/commit/eb381b9444c6b1ec78414d1c9375...
deleted 11y ago
[deleted]
TazeTSchnitzel 11y ago
> 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.

TazeTSchnitzel 11y ago

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