6 ms·

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/co

by pygy_ 11y ago

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/623cbdc5432713badc9fe1d605c585aabb25876c https://github.com/v8/v8/commit/623cbdc5432713badc9fe1d605c5... 1. https://codereview.chromium.org/1462293002/#msg12 https://codereview.chromium.org/1462293002/#msg12

je42 11y ago
I don't understand why they don't go for mersenne twister ?!
- acqq 11y ago
  MT is "on average" maybe "as fast" but the key is "on average:" depending on the usage pattern it can cost much more. 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.
- bhickey 11y ago
  I haven't looked closely enough at their choice to evaluate it, but there's a good reason not to use Mersenne Twister. MT is a bad generator. * 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.
  - acqq 11y ago
    The best advice of all I've seen in the comments here. The PCG page: http://www.pcg-random.org/ http://www.pcg-random.org/ contains a nice comparison table.
  - adrae5df 11y ago
    Can you name those rudimentary statistical tests that Mersenne Twister fails. I would like to test them out, since I regularly use MT. Thank you.
    - acqq 11y ago
      Apparently here: https://en.m.wikipedia.org/wiki/TestU01 https://en.m.wikipedia.org/wiki/TestU01 Wikipedia entry for MT specifies some of the problems.
      - adrae5df 11y ago
        The entire TestU01? Wow, I did not know that.
        acqq 11y ago
        I thought you were interested to find the tests. The tests that fail are there. MT doesn't fail all, far from it. But there are RNGs that don't fail these that MT fails that are faster. PCG was mentioned here.
        adrae5df 11y ago
        The only information on PCG I can find is the author's own paper which also fails some TestU01 tests. I am much more inclined to trust an established generator than an unproved one.
        bhickey 11y ago
        PCG is a family of PRNGs. Any sensible member of the family will trivially pass TestU01 BigCrush. If you use a 32-bit PCG it's going to necessarily fail BigCrush. 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.
acqq 11y ago
Did anybody make any tests of the resulting streams and compared the period and the properties? The code which inspired the article is obviously able to discover certain weaknesses.
hacst 11y ago
I must be missing some communication medium / tracker reference or is the information listed in the code-review really all there is on this change? Full commit message: "Tweak RNG." Reviewer comment: "LGTM" landed No reason for the change, no source code comment, no discussion?
deckar01 11y ago
A commit that is 90% refactoring and 10% critical system changes is a sin. Don't hide the important stuff, separate refactoring into its own commit.

by pygy_ 11y ago

je42 11y ago

I don't understand why they don't go for mersenne twister ?!

acqq 11y ago
MT is "on average" maybe "as fast" but the key is "on average:" depending on the usage pattern it can cost much more. 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.
bhickey 11y ago
I haven't looked closely enough at their choice to evaluate it, but there's a good reason not to use Mersenne Twister. MT is a bad generator. * 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.
- acqq 11y ago
  The best advice of all I've seen in the comments here. The PCG page: http://www.pcg-random.org/ http://www.pcg-random.org/ contains a nice comparison table.
- adrae5df 11y ago
  Can you name those rudimentary statistical tests that Mersenne Twister fails. I would like to test them out, since I regularly use MT. Thank you.
  - acqq 11y ago
    Apparently here: https://en.m.wikipedia.org/wiki/TestU01 https://en.m.wikipedia.org/wiki/TestU01 Wikipedia entry for MT specifies some of the problems.
    - adrae5df 11y ago
      The entire TestU01? Wow, I did not know that.
      - acqq 11y ago
        I thought you were interested to find the tests. The tests that fail are there. MT doesn't fail all, far from it. But there are RNGs that don't fail these that MT fails that are faster. PCG was mentioned here.
        adrae5df 11y ago
        The only information on PCG I can find is the author's own paper which also fails some TestU01 tests. I am much more inclined to trust an established generator than an unproved one.
        bhickey 11y ago
        PCG is a family of PRNGs. Any sensible member of the family will trivially pass TestU01 BigCrush. If you use a 32-bit PCG it's going to necessarily fail BigCrush. 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.

acqq 11y ago

Did anybody make any tests of the resulting streams and compared the period and the properties? The code which inspired the article is obviously able to discover certain weaknesses.

hacst 11y ago

I must be missing some communication medium / tracker reference or is the information listed in the code-review really all there is on this change? Full commit message: "Tweak RNG." Reviewer comment: "LGTM" landed No reason for the change, no source code comment, no discussion?

deckar01 11y ago

A commit that is 90% refactoring and 10% critical system changes is a sin. Don't hide the important stuff, separate refactoring into its own commit.