13 ms·

There's Math.random(), and then there's Math.random()

229 points by v33ra 11y ago

dspillett 11y ago
Do be sure to note the mention that the new algorithm is not considered a cryptographically secure PRNG. Also because the specification has very little by way of requirements in that regard, no matter how good some implementations may be you should always assume you code may end up being used in an environment where Math.random() is no better than the worst generator you can think of. If you need specific properties in your PRNG then you still need to provide something in place of Math.random().
- danbolt 11y ago
  This is good to think about! Often when programming games that need certain properties, I'll write my own toy PRNG, but I'll admit I'd love to learn more about the craft. Would you have any suggested reading material on the topic?
  - resc1440 11y ago
    As an outsider to the field, I really enjoyed reading this paper: http://www.pcg-random.org/paper.html http://www.pcg-random.org/paper.html It's advocating for a particular new kind of PRNG, but it also includes a lot of great explanations and citations for more reading.
    - yoklov 11y ago
      As a shameless plug, I wrote a JS port of this RNG algorithm a while back: https://www.npmjs.com/package/pcg-random https://www.npmjs.com/package/pcg-random .
  - PhantomGremlin 11y ago
    any suggested reading material on the topic? The Art of Computer Programming, Vol. 2, (c) 1969, by Donald Knuth, has quite an extensive discussion of random numbers, their properties, algorithms, and tests. It's about 160 pages in my edition. It's very readable, and even if you skip all the exercises you will still get a very good grounding. I don't know how much has changed in his more recent editions. And I don't know how if there are better books. But, in general, you can't go wrong by starting with Knuth. He's one of the all time greats!
  - yoklov 11y ago
    For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game).
    - zeveb 11y ago
      For a modern game, is there any particular reason why 'seed = SHA256(seed + "reseed"); return SHA256(seed + "value")' isn't a good enough, performant enough RNG?
      - vonmoltke 11y ago
        For starters, there is nothing random about it.
        zeveb 11y ago
        > For starters, there is nothing random about it. Yes, since the original post wanted seedability: > > For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game). Given that restriction, what's wrong with the generator I suggest?
        vonmoltke 11y ago
        It's not random. It's not a generator. You are just returning a different representation of the seed you already have.
        zeveb 11y ago
        > It's not random. It's not a generator. No, it's a pseudorandom generator. It's a key attribute of a cryptographically secure function like SHA256 that its output is indistinguishable from random bits. > You are just returning a different representation of the seed you already have. I'm returning a function of the seed, yes. That's the whole point of a seeded PRNG: that seed(x); rng(); rng(); rng() will always return the same sequence of results. This is used for example in procedural generation, to ensure that a dungeon level or map chunk is always generated the same way (a cool hack, then, is to just store the seed instead of the level itself, and rerun the level-generation algorithm with the seed when one wishes to regenerate the level). In such an application one wants the appearance of randomness, but with repeatability. Which was what the original post asked for. What I suggested is not secure for generating keys or for other cryptographic purposes.
  - malingo 11y ago
    This is a great 2-part article: http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand...
- neerdowell 11y ago
  > the worst generator you can think of Decrementing the seed by 1 with each call[0], which is a standards-compliant rand implementation. Although it looks like a standards-compliant Math.random() implementation isn't allowed to be quite that bad[1]. [0] https://marc.info/?l=openbsd-tech&m=141773078029373&w=2 https://marc.info/?l=openbsd-tech&m=141773078029373&w=2 [1] http://www.ecma-international.org/ecma-262/5.1/#sec-15.8.2.14 http://www.ecma-international.org/ecma-262/5.1/#sec-15.8.2.1...
  - tlrobinson 11y ago
    Obligatory XKCD: https://xkcd.com/221/ https://xkcd.com/221/
- tlrobinson 11y ago
  This is the most important point. I didn't like that "TIFU by using Math.random()" article because it felt like it was deflecting some of the blame by focusing so much on the details of V8's PRNG, when it reality it's 100% his fault for not using a CSPRNG (in a gambling application, no less).
  - WatchDog 11y ago
    His application was using the RNG to avoid collisions in high performance random ID generation. Without knowing more about the system, it seems like a good case for a good non-CSPRNG.
- jameshart 11y ago
  All true. And the 'specific properties' you might need might not be cryptographic security. For example, I did some stuff recently in Javascript with procedural generation that made heavy use of random numbers. I used my own implementation of a mersenne twister, rather than Math.random, precisely so I could have predictable long term and cross-engine repeatability of the random number sequences generated based on the same seed. So how good does the default random number routine in JavaScript really need to be?
ifcologne 11y ago
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)
Someone1234 11y ago
This article[0] hints that Microsoft's Edge browser might also being using MWC1616, or something else that has a lot of the same limitations. Hopefully they jump on the xorshift128+ ship. [0] https://lwn.net/Articles/666407/ https://lwn.net/Articles/666407/
- sanxiyn 11y ago
  The article actually hints that Firefox (not Chrome) and Edge used the same RNG. The article says "LCG imported from Java decades ago", but actually Java(OpenJDK)'s java.util.Random still uses the same RNG today, and it's not that surprising Edge also used it. The generator (LCG with multiplier 0x5DEECE66D) is not bad. Its main problem is that it has only 48 bits of state.
nathan_long 11y ago
I wondered how the "static" visualizations were produced, then noticed the link under the image: http://bl.ocks.org/mmalone/bf59aa2e44c44dde78ac http://bl.ocks.org/mmalone/bf59aa2e44c44dde78ac There you can see the code and watch it run. Neat!
nraynaud 11y ago
>"Please keep in mind, if you find areas of improvement in V8 and Chrome, even ones that—like this one—do not directly affect spec compliance, stability, or security, please file an issue on our bug tracker." Worst idea ever, this not-a-real-bug got a correction in just a few days without even being in the bug tracker, while there are real bugs stalled for years in the tracker. Writing a blog post and making a lot of noise on the internet works way better than using the bug tracker.
- nolok 11y ago
  Wrong, making a bug report then being taken up on it is much better than publishing the issue as:is
  - serge2k 11y ago
    Why?
  - kevingadd 11y ago
    This RNG problem had a bug report with hundreds of comments where a v8 dev downplayed its importance and insisted it shouldn't be fixed. So, bad example.
    - magicalist 11y ago
      Where is that? There have been other issues where this has happened (like the infamous trig optimization bug), but I'm not aware of one for Math.random(). It's also worth noting that a good number of people (like [1]) outside of the V8 team were also skeptical because of lack of specification for the RNG, speed downsides to switching, and the availability of a CSPRNG in the browser and node. You can argue that they're wrong, but that's not immediately clear, Bug reports sometimes become that site of those arguments, and sometimes even the right arguments end up losing a round and having to come back in when the right people are noticing. Working as intended. Regardless, the blog post or bug report dichotomy is a false one anyways, as obviously you can write a blog post and file a bug (as Mike later said he meant to). It's not like he was assailing the V8 team or something. The post was written a little dramatically, but he was engaged with the team in the followup bug (filed by a V8 dev) and elsewhere. [1] https://mobile.twitter.com/sleevi_/status/667636624256344064 https://mobile.twitter.com/sleevi_/status/667636624256344064
evilpie 11y ago
Jan also wrote about this http://jandemooij.nl/blog/2015/11/27/math-random-and-32-bit-precision/ http://jandemooij.nl/blog/2015/11/27/math-random-and-32-bit-... in the context of Spidermonkey.
mring33621 11y ago
Pretty sure I saw the 'After' picture in the mall, circa 1992. If you cross your eyes and look 'through' it just right, you'll see the sailboat.
- AaronBBrown 11y ago
  It's not a schooner, it's a sailboat!
- ChrisArchitect 11y ago
  nah man, it's Blonde, Brunette, Redhead...
cdnsteve 11y ago
This kind of stuff seems scary to me. One JavaScript engine decides to use this algorithm, another that. This type of change could lead to higher potential of bugs and unexpected behaviour, the average developer just can't figure out when say, using Firefox or Chrome for testing. When algorithms are getting tinkered with behind the scenes, this leads me to believe there's still way too much churn in the JS space.
- spicyj 11y ago
  OSes don't guarantee exactly how rand() behaves, do they?
  - masklinn 11y ago
    rand(3) isn't really the OS's concern, it's part of POSIX and the C standard which don't indeed, but could. Java specifies exactly how java.util.Random should be implemented (LCG from TAOCP with a 48 bit seed), which on the one hand means its well-understood and stable across machines, and on the other hand means it's kinda crap and can't ever be upgraded.
    - mmalone 11y ago
      Yep and with the new SplittableRandom they seem to have opted for a more subjective definition with a guaranteed minimum cycle length and passing marks on Diehard. Seems like a happy middle ground.
- geofft 11y ago
  It's a random-number generator. It's not supposed to have expected behavior.
  - TheOtherHobbes 11y ago
    If it's a seedable generator, it certainly is. There are applications in creative coding and gaming where it's critical to have a reproducible random sequence that gives the same results on all platforms.
zeveb 11y ago
It seems to me that defaulting to a non-CSPRNG these days is a premature optimization: for many purposes a decent CSPRNG (e.g. Fortuna) is fast enough, and avoids all the pitfalls of a non-secure or poorly-random generator. Maybe it's time to have Math.random and equivalents call a CSPRNG, with a Math.insecurerandom when performance matters?
- geofft 11y ago
  Are there any use cases for which a good CSPRNG, with a fixed 256-bit seed at process startup from /dev/urandom or equivalent, is not fast enough? Last time this came up on HN, I measured individual reads from /dev/urandom, and those are fast enough for many large-scale applications, like one per tweet: https://news.ycombinator.com/item?id=10608843 https://news.ycombinator.com/item?id=10608843 (Obviously there are bad CSPRNGs, but there are also bad non-CS PRNGs. So let's not count those.)
  - masklinn 11y ago
    One major issue is much of the "fast enough" problem is about benchmarks, and possibly even microbenchmarks. When a popular benchmark (or some rando's microbenchmark) really just exercises the RNG, the headline will still be "$FOO IS SLOW AS MOLASSES AND THAT'S BULLSHIT" not "$foo courageously uses a non-garbage RNG by default despite some performance impact in RNG-heavy scenarios". So the primary incentive for language/stdlib developers is to have a fast rng, not to have a good one. They probably aren't going to sabotage the rng entirely, but given the choice between "fast and same as everybody else" or "excellent but not as fast" chances are the first one will win, even if it's crap. The same problem exists with hash functions.
    - geofft 11y ago
      Hash functions are supposed to be fast, though. (If you need something slow like a keystretching function, you iterate a hash function, and you pick the number of iterations based on wall clock time on a representative machine.) BLAKE2 is competitive with MD5 and way, way more secure, for instance: https://blake2.net/ https://blake2.net/
stevebmark 11y ago
The first one looks more random to me? It has more runs. There was some article (can't remember the source) about generating a random coin flip - the way to tell the difference between a real physical coin flip and a computer is that the real physical flip will have a lot of runs, like 10 times in a row where you get heads. A computer random will attempt to "even out" the spectrum. The two images presented in the article looked similar to these but were reversed, true random looked more like a pattern, while computer generated random looked more like even noise. TL;DR long strings of repeated results are a sign of true randomness. Am I misinterpreting the relationship between that and this article?
- russellsprouts 11y ago
  That's true in general, but note that the runs should show up in 2 dimensions in the image. The second one appears clumpy, which exactly what it should look like. People tend to avoid runs, which would make it look more uniform. The first one has an obvious bias because it doesn't look the same in the x direction as in the y.
- dchest 11y ago
  Randomness looks like white noise. You can't distinguish computer randomness (provided that it's a proper PRNG) from physical coin flips. Computers don't "even out spectrum". The longer the coin flip run, the less likely it is to happen, e.g. you would need on average 2046 coin throws to get 10 heads in a row. TL;DR probability theory (If you have free time and want to have some fun, throw a coin and draw a picture recording throws. I once generated a password by throwing a coin for more than hundred or times — each bit taking more than 1 throw to avoid biases — https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_...)
  - pakitan 11y ago
    > Computers don't "even out spectrum" Not "on purpose", of course. But with a bad PRNG, the probability of 10 heads in a row is lower compared to a proper PRNG so in a sense the bad one is "evening out spectrum"
dvt 11y ago
Somewhat related, I wrote a blog post about (P)RNGs a few years ago: http://dvt.name/2010/clock-drift-hardware-prng/ http://dvt.name/2010/clock-drift-hardware-prng/. It's interesting to se V8 favor accuracy over speed. I'd think that having a "secure" random number generator isn't that important of a deal given the fact that all code runs client-side anyway (so why the need for cryptographic security?).
- IgorPartola 11y ago
  So in one application I have I use Math.random() as a fallback when window.crypto isn't available to generate UUID's. I am less concerned with security, and more concerned with collisions between different clients. Making Math.random() more uniform helps with that, though only marginally since browsers that did that also support window.crypto.
- zeta0134 11y ago
  That's actually not always true. Any application running on node.js is using the V8 engine as it's serverside backend, and might thusly be affected. There are also a handful of applications that do clientside encryption. (MEGA comes to mind, someone here should chime in with a better example.) Just because the use case is uncommon doesn't make it invalid.
  - alanh 11y ago
    > Just because the use case is uncommon doesn't make it invalid. Yes! Designers of systems, APIs, and user interfaces should adopt this as a sort of mantra.
  - dvt 11y ago
    Fair enough, wasn't thinking of Node.js.
cookiemonsta 11y ago
I didn't realise JS's Math.random() really wasn't quite so random...
jacobolus 11y ago
Is there an explanation anywhere of what technical or other criteria they used to pick xorshift128+? I haven’t seen any from the handful of blog posts, etc. I’ve seen about the change. “[...] having understood the problem and after some research, we decided [...]” is hardly a persuasive analysis. Were any professional experts on PRNGs asked for advice?
blixt 11y ago
For people concerned with cross-browser reproducibility as well as resuming a PRNG between sessions (e.g., to reproduce random sequences in replays or multiplayer), check out arbit, an NPM package I made. It performs close to Math.random and uses floats for state internally for max resolution (i.e., length and number of unique sequences): https://github.com/blixt/js-arbit https://github.com/blixt/js-arbit I would also recommend running the provided DieHarder test, which is crafted to measure the quality of PRNGs.
jakub_g 11y ago
Previous discussion (from one month ago) on the referred article with discovery of the bug: https://news.ycombinator.com/item?id=10598065 https://news.ycombinator.com/item?id=10598065

229 points by v33ra 11y ago

Do be sure to note the mention that the new algorithm is not considered a cryptographically secure PRNG. Also because the specification has very little by way of requirements in that regard, no matter how good some implementations may be you should always assume you code may end up being used in an environment where Math.random() is no better than the worst generator you can think of. If you need specific properties in your PRNG then you still need to provide something in place of Math.random().

danbolt 11y ago
This is good to think about! Often when programming games that need certain properties, I'll write my own toy PRNG, but I'll admit I'd love to learn more about the craft. Would you have any suggested reading material on the topic?
- resc1440 11y ago
  As an outsider to the field, I really enjoyed reading this paper: http://www.pcg-random.org/paper.html http://www.pcg-random.org/paper.html It's advocating for a particular new kind of PRNG, but it also includes a lot of great explanations and citations for more reading.
  - yoklov 11y ago
    As a shameless plug, I wrote a JS port of this RNG algorithm a while back: https://www.npmjs.com/package/pcg-random https://www.npmjs.com/package/pcg-random .
- PhantomGremlin 11y ago
  any suggested reading material on the topic? The Art of Computer Programming, Vol. 2, (c) 1969, by Donald Knuth, has quite an extensive discussion of random numbers, their properties, algorithms, and tests. It's about 160 pages in my edition. It's very readable, and even if you skip all the exercises you will still get a very good grounding. I don't know how much has changed in his more recent editions. And I don't know how if there are better books. But, in general, you can't go wrong by starting with Knuth. He's one of the all time greats!
- yoklov 11y ago
  For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game).
  - zeveb 11y ago
    For a modern game, is there any particular reason why 'seed = SHA256(seed + "reseed"); return SHA256(seed + "value")' isn't a good enough, performant enough RNG?
    - vonmoltke 11y ago
      For starters, there is nothing random about it.
      - zeveb 11y ago
        > For starters, there is nothing random about it. Yes, since the original post wanted seedability: > > For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game). Given that restriction, what's wrong with the generator I suggest?
        vonmoltke 11y ago
        It's not random. It's not a generator. You are just returning a different representation of the seed you already have.
        zeveb 11y ago
        > It's not random. It's not a generator. No, it's a pseudorandom generator. It's a key attribute of a cryptographically secure function like SHA256 that its output is indistinguishable from random bits. > You are just returning a different representation of the seed you already have. I'm returning a function of the seed, yes. That's the whole point of a seeded PRNG: that seed(x); rng(); rng(); rng() will always return the same sequence of results. This is used for example in procedural generation, to ensure that a dungeon level or map chunk is always generated the same way (a cool hack, then, is to just store the seed instead of the level itself, and rerun the level-generation algorithm with the seed when one wishes to regenerate the level). In such an application one wants the appearance of randomness, but with repeatability. Which was what the original post asked for. What I suggested is not secure for generating keys or for other cryptographic purposes.
- malingo 11y ago
  This is a great 2-part article: http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand...
neerdowell 11y ago
> the worst generator you can think of Decrementing the seed by 1 with each call[0], which is a standards-compliant rand implementation. Although it looks like a standards-compliant Math.random() implementation isn't allowed to be quite that bad[1]. [0] https://marc.info/?l=openbsd-tech&m=141773078029373&w=2 https://marc.info/?l=openbsd-tech&m=141773078029373&w=2 [1] http://www.ecma-international.org/ecma-262/5.1/#sec-15.8.2.14 http://www.ecma-international.org/ecma-262/5.1/#sec-15.8.2.1...
- tlrobinson 11y ago
  Obligatory XKCD: https://xkcd.com/221/ https://xkcd.com/221/
tlrobinson 11y ago
This is the most important point. I didn't like that "TIFU by using Math.random()" article because it felt like it was deflecting some of the blame by focusing so much on the details of V8's PRNG, when it reality it's 100% his fault for not using a CSPRNG (in a gambling application, no less).
- WatchDog 11y ago
  His application was using the RNG to avoid collisions in high performance random ID generation. Without knowing more about the system, it seems like a good case for a good non-CSPRNG.
jameshart 11y ago
All true. And the 'specific properties' you might need might not be cryptographic security. For example, I did some stuff recently in Javascript with procedural generation that made heavy use of random numbers. I used my own implementation of a mersenne twister, rather than Math.random, precisely so I could have predictable long term and cross-engine repeatability of the random number sequences generated based on the same seed. So how good does the default random number routine in JavaScript really need to be?

ifcologne 11y ago

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)

Someone1234 11y ago

This article[0] hints that Microsoft's Edge browser might also being using MWC1616, or something else that has a lot of the same limitations. Hopefully they jump on the xorshift128+ ship. [0] https://lwn.net/Articles/666407/ https://lwn.net/Articles/666407/

sanxiyn 11y ago
The article actually hints that Firefox (not Chrome) and Edge used the same RNG. The article says "LCG imported from Java decades ago", but actually Java(OpenJDK)'s java.util.Random still uses the same RNG today, and it's not that surprising Edge also used it. The generator (LCG with multiplier 0x5DEECE66D) is not bad. Its main problem is that it has only 48 bits of state.

nathan_long 11y ago

I wondered how the "static" visualizations were produced, then noticed the link under the image: http://bl.ocks.org/mmalone/bf59aa2e44c44dde78ac http://bl.ocks.org/mmalone/bf59aa2e44c44dde78ac There you can see the code and watch it run. Neat!

nraynaud 11y ago

>"Please keep in mind, if you find areas of improvement in V8 and Chrome, even ones that—like this one—do not directly affect spec compliance, stability, or security, please file an issue on our bug tracker." Worst idea ever, this not-a-real-bug got a correction in just a few days without even being in the bug tracker, while there are real bugs stalled for years in the tracker. Writing a blog post and making a lot of noise on the internet works way better than using the bug tracker.

nolok 11y ago
Wrong, making a bug report then being taken up on it is much better than publishing the issue as:is
- serge2k 11y ago
  Why?
- kevingadd 11y ago
  This RNG problem had a bug report with hundreds of comments where a v8 dev downplayed its importance and insisted it shouldn't be fixed. So, bad example.
  - magicalist 11y ago
    Where is that? There have been other issues where this has happened (like the infamous trig optimization bug), but I'm not aware of one for Math.random(). It's also worth noting that a good number of people (like [1]) outside of the V8 team were also skeptical because of lack of specification for the RNG, speed downsides to switching, and the availability of a CSPRNG in the browser and node. You can argue that they're wrong, but that's not immediately clear, Bug reports sometimes become that site of those arguments, and sometimes even the right arguments end up losing a round and having to come back in when the right people are noticing. Working as intended. Regardless, the blog post or bug report dichotomy is a false one anyways, as obviously you can write a blog post and file a bug (as Mike later said he meant to). It's not like he was assailing the V8 team or something. The post was written a little dramatically, but he was engaged with the team in the followup bug (filed by a V8 dev) and elsewhere. [1] https://mobile.twitter.com/sleevi_/status/667636624256344064 https://mobile.twitter.com/sleevi_/status/667636624256344064

evilpie 11y ago

Jan also wrote about this http://jandemooij.nl/blog/2015/11/27/math-random-and-32-bit-precision/ http://jandemooij.nl/blog/2015/11/27/math-random-and-32-bit-... in the context of Spidermonkey.

mring33621 11y ago

Pretty sure I saw the 'After' picture in the mall, circa 1992. If you cross your eyes and look 'through' it just right, you'll see the sailboat.

AaronBBrown 11y ago
It's not a schooner, it's a sailboat!
ChrisArchitect 11y ago
nah man, it's Blonde, Brunette, Redhead...

cdnsteve 11y ago

This kind of stuff seems scary to me. One JavaScript engine decides to use this algorithm, another that. This type of change could lead to higher potential of bugs and unexpected behaviour, the average developer just can't figure out when say, using Firefox or Chrome for testing. When algorithms are getting tinkered with behind the scenes, this leads me to believe there's still way too much churn in the JS space.

spicyj 11y ago
OSes don't guarantee exactly how rand() behaves, do they?
- masklinn 11y ago
  rand(3) isn't really the OS's concern, it's part of POSIX and the C standard which don't indeed, but could. Java specifies exactly how java.util.Random should be implemented (LCG from TAOCP with a 48 bit seed), which on the one hand means its well-understood and stable across machines, and on the other hand means it's kinda crap and can't ever be upgraded.
  - mmalone 11y ago
    Yep and with the new SplittableRandom they seem to have opted for a more subjective definition with a guaranteed minimum cycle length and passing marks on Diehard. Seems like a happy middle ground.
geofft 11y ago
It's a random-number generator. It's not supposed to have expected behavior.
- TheOtherHobbes 11y ago
  If it's a seedable generator, it certainly is. There are applications in creative coding and gaming where it's critical to have a reproducible random sequence that gives the same results on all platforms.

zeveb 11y ago

It seems to me that defaulting to a non-CSPRNG these days is a premature optimization: for many purposes a decent CSPRNG (e.g. Fortuna) is fast enough, and avoids all the pitfalls of a non-secure or poorly-random generator. Maybe it's time to have Math.random and equivalents call a CSPRNG, with a Math.insecurerandom when performance matters?

geofft 11y ago
Are there any use cases for which a good CSPRNG, with a fixed 256-bit seed at process startup from /dev/urandom or equivalent, is not fast enough? Last time this came up on HN, I measured individual reads from /dev/urandom, and those are fast enough for many large-scale applications, like one per tweet: https://news.ycombinator.com/item?id=10608843 https://news.ycombinator.com/item?id=10608843 (Obviously there are bad CSPRNGs, but there are also bad non-CS PRNGs. So let's not count those.)
- masklinn 11y ago
  One major issue is much of the "fast enough" problem is about benchmarks, and possibly even microbenchmarks. When a popular benchmark (or some rando's microbenchmark) really just exercises the RNG, the headline will still be "$FOO IS SLOW AS MOLASSES AND THAT'S BULLSHIT" not "$foo courageously uses a non-garbage RNG by default despite some performance impact in RNG-heavy scenarios". So the primary incentive for language/stdlib developers is to have a fast rng, not to have a good one. They probably aren't going to sabotage the rng entirely, but given the choice between "fast and same as everybody else" or "excellent but not as fast" chances are the first one will win, even if it's crap. The same problem exists with hash functions.
  - geofft 11y ago
    Hash functions are supposed to be fast, though. (If you need something slow like a keystretching function, you iterate a hash function, and you pick the number of iterations based on wall clock time on a representative machine.) BLAKE2 is competitive with MD5 and way, way more secure, for instance: https://blake2.net/ https://blake2.net/

stevebmark 11y ago

The first one looks more random to me? It has more runs. There was some article (can't remember the source) about generating a random coin flip - the way to tell the difference between a real physical coin flip and a computer is that the real physical flip will have a lot of runs, like 10 times in a row where you get heads. A computer random will attempt to "even out" the spectrum. The two images presented in the article looked similar to these but were reversed, true random looked more like a pattern, while computer generated random looked more like even noise. TL;DR long strings of repeated results are a sign of true randomness. Am I misinterpreting the relationship between that and this article?

russellsprouts 11y ago
That's true in general, but note that the runs should show up in 2 dimensions in the image. The second one appears clumpy, which exactly what it should look like. People tend to avoid runs, which would make it look more uniform. The first one has an obvious bias because it doesn't look the same in the x direction as in the y.
dchest 11y ago
Randomness looks like white noise. You can't distinguish computer randomness (provided that it's a proper PRNG) from physical coin flips. Computers don't "even out spectrum". The longer the coin flip run, the less likely it is to happen, e.g. you would need on average 2046 coin throws to get 10 heads in a row. TL;DR probability theory (If you have free time and want to have some fun, throw a coin and draw a picture recording throws. I once generated a password by throwing a coin for more than hundred or times — each bit taking more than 1 throw to avoid biases — https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_...)
- pakitan 11y ago
  > Computers don't "even out spectrum" Not "on purpose", of course. But with a bad PRNG, the probability of 10 heads in a row is lower compared to a proper PRNG so in a sense the bad one is "evening out spectrum"

dvt 11y ago

Somewhat related, I wrote a blog post about (P)RNGs a few years ago: http://dvt.name/2010/clock-drift-hardware-prng/ http://dvt.name/2010/clock-drift-hardware-prng/. It's interesting to se V8 favor accuracy over speed. I'd think that having a "secure" random number generator isn't that important of a deal given the fact that all code runs client-side anyway (so why the need for cryptographic security?).

IgorPartola 11y ago
So in one application I have I use Math.random() as a fallback when window.crypto isn't available to generate UUID's. I am less concerned with security, and more concerned with collisions between different clients. Making Math.random() more uniform helps with that, though only marginally since browsers that did that also support window.crypto.
zeta0134 11y ago
That's actually not always true. Any application running on node.js is using the V8 engine as it's serverside backend, and might thusly be affected. There are also a handful of applications that do clientside encryption. (MEGA comes to mind, someone here should chime in with a better example.) Just because the use case is uncommon doesn't make it invalid.
- alanh 11y ago
  > Just because the use case is uncommon doesn't make it invalid. Yes! Designers of systems, APIs, and user interfaces should adopt this as a sort of mantra.
- dvt 11y ago
  Fair enough, wasn't thinking of Node.js.

cookiemonsta 11y ago

I didn't realise JS's Math.random() really wasn't quite so random...

jacobolus 11y ago

Is there an explanation anywhere of what technical or other criteria they used to pick xorshift128+? I haven’t seen any from the handful of blog posts, etc. I’ve seen about the change. “[...] having understood the problem and after some research, we decided [...]” is hardly a persuasive analysis. Were any professional experts on PRNGs asked for advice?

blixt 11y ago

For people concerned with cross-browser reproducibility as well as resuming a PRNG between sessions (e.g., to reproduce random sequences in replays or multiplayer), check out arbit, an NPM package I made. It performs close to Math.random and uses floats for state internally for max resolution (i.e., length and number of unique sequences): https://github.com/blixt/js-arbit https://github.com/blixt/js-arbit I would also recommend running the provided DieHarder test, which is crafted to measure the quality of PRNGs.

jakub_g 11y ago

Previous discussion (from one month ago) on the referred article with discovery of the bug: https://news.ycombinator.com/item?id=10598065 https://news.ycombinator.com/item?id=10598065