5 ms·

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

by je42 11y ago

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.
- SeanLuke 11y ago
  I wouldn't touch PCG yet. It's based on a single paper submitted to a journal which hasn't even been reviewed yet. Has there been any independent testing of the algorithm? Not that I know of. And the entire PCG website appears to have been built by the paper author as a promotional tool, which is a bit spooky given that the paper hasn't even been published. MT is far from a "bad generator". It doesn't pass a few stringent TestU01 tests, which is the case for a number of very well regarded generators.
  - adrae5df 11y ago
    I was just researching PCG, and I didn't find anything relevant apart from the the author's paper and website. I was trying to find out if it has been peer reviewed since its release last year. I'm really curious, how did you check if this paper was peer reviewed?
  - bhickey 11y ago
    What failure mode are you worried about? Yes, the author has a definite incentive to self-promote. At the same time she's produced a testable artifact. I think her claims about predictability are bogus, but the rest of it we can trivially verify on the merits. Simple PCG PRNGs are fast and pass TestU01 BigCrush. Someone could conceivably cook up a new battery of tests that it fails on, but we'd need to reevaluate the whole zoology of RNGs at this point. Edit: Sorry, I was playing loose classifying MT's BigCrush failures as rudimentary. That said, I think failing any part of BigCrush should disqualify a PRNG from use.
    - SeanLuke 11y ago
      > That said, I think failing any part of BigCrush should disqualify a PRNG from use. Would include the PCG family then?
      - bhickey 11y ago
        No, it isn't a reasonable comparison: PCG is a family while MT is particular Generalized Feedback Shift Register. Despite my suspicions I can't tell you off the top of my head if the entire GFSR class is dodgy, but we can point out flaws in a single generator. I buy O'Neill's arguments (other than those about security, which are a load of hooey) and I think added scrutiny will bear her out. Usually what I see is people flocking to MT because of its comically large period When it comes down to it, PRNG quality gets assessed empirically. Why would you use ever a generator with 2kb of state when faster & smaller generators like PCG or Xorshift* pass the same statistical battery? You can also write proofs about their behavior to ferret out the lousy ones. For example, we can demonstrate that PCG is full period. Consider the inner LCG: x1 = (ax0 + c) % m The modulus term is equivalent to the size of `x`, so in practice you can skip it and rely on overflow. By requiring that `c` is odd and `m` is a power of two, we know that `c` and `m` are coprime. If you select `a` such that (a - 1) % 4 = 0, the inner LCG is full period. If you look at the permutation function, it's also provably unbiased by counting. Since all possible bit sequences are fairly represented in the PCG state we know that all combinations of permuting bits appear with all possible output bits.

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

by 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.
SeanLuke 11y ago
I wouldn't touch PCG yet. It's based on a single paper submitted to a journal which hasn't even been reviewed yet. Has there been any independent testing of the algorithm? Not that I know of. And the entire PCG website appears to have been built by the paper author as a promotional tool, which is a bit spooky given that the paper hasn't even been published. MT is far from a "bad generator". It doesn't pass a few stringent TestU01 tests, which is the case for a number of very well regarded generators.
- adrae5df 11y ago
  I was just researching PCG, and I didn't find anything relevant apart from the the author's paper and website. I was trying to find out if it has been peer reviewed since its release last year. I'm really curious, how did you check if this paper was peer reviewed?
- bhickey 11y ago
  What failure mode are you worried about? Yes, the author has a definite incentive to self-promote. At the same time she's produced a testable artifact. I think her claims about predictability are bogus, but the rest of it we can trivially verify on the merits. Simple PCG PRNGs are fast and pass TestU01 BigCrush. Someone could conceivably cook up a new battery of tests that it fails on, but we'd need to reevaluate the whole zoology of RNGs at this point. Edit: Sorry, I was playing loose classifying MT's BigCrush failures as rudimentary. That said, I think failing any part of BigCrush should disqualify a PRNG from use.
  - SeanLuke 11y ago
    > That said, I think failing any part of BigCrush should disqualify a PRNG from use. Would include the PCG family then?
    - bhickey 11y ago
      No, it isn't a reasonable comparison: PCG is a family while MT is particular Generalized Feedback Shift Register. Despite my suspicions I can't tell you off the top of my head if the entire GFSR class is dodgy, but we can point out flaws in a single generator. I buy O'Neill's arguments (other than those about security, which are a load of hooey) and I think added scrutiny will bear her out. Usually what I see is people flocking to MT because of its comically large period When it comes down to it, PRNG quality gets assessed empirically. Why would you use ever a generator with 2kb of state when faster & smaller generators like PCG or Xorshift* pass the same statistical battery? You can also write proofs about their behavior to ferret out the lousy ones. For example, we can demonstrate that PCG is full period. Consider the inner LCG: x1 = (ax0 + c) % m The modulus term is equivalent to the size of `x`, so in practice you can skip it and rely on overflow. By requiring that `c` is odd and `m` is a power of two, we know that `c` and `m` are coprime. If you select `a` such that (a - 1) % 4 = 0, the inner LCG is full period. If you look at the permutation function, it's also provably unbiased by counting. Since all possible bit sequences are fairly represented in the PCG state we know that all combinations of permuting bits appear with all possible output bits.