News for hackers. Stuff that matters.
Re:Math.random in V8 is broken by SeanLuke on Saturday November 21, 2015 @12:14PM (#10607299)
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.

Re:Math.random in V8 is broken by bhickey on Saturday November 21, 2015 @06:02PM (#10608388)
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.

Re:Math.random in V8 is broken by SeanLuke on Saturday November 21, 2015 @10:36PM (#10608972)
> That said, I think failing any part of BigCrush should disqualify a PRNG from use.

Would include the PCG family then?

Re:Math.random in V8 is broken by bhickey on Saturday November 21, 2015 @11:20PM (#10609064)
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.

Re:Math.random in V8 is broken by adrae5df on Saturday November 21, 2015 @12:26PM (#10607350)
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?