6 ms·

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 t

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.

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.