The wrap-up on PCG generators

[Sebastiano Vigna]

For those who might be interested, I put together a review of PCG generators.

http://pcg.di.unimi.it/pcg.php

It gather a few sparse comments I made in discussions here and elsewhere.

Ciao,

seba

[albert...@yahoo.com]

Nice job on http://pcg.di.unimi.it/predpcg.c

pcg32 solving time in half hour ?
Amazing !

I once try a naive pcg32 solve using Python z3
Estimated solving time is about a week.

[albert...@yahoo.com]

> Half an hour it's the time to write the program. Prediction takes a few seconds...
>
> -- Vigna

The description is somewhat misleading:

... Note that it is impossible to approach the problem by brute force:
to try blindly all possible 264 states you would need centuries of time.

The function that performs the prediction, recover(), took maybe half an hour of effort.
It's a couple of loops, a couple of if's and a few logical operations ...

[Chris Rutz]

Does your analysis of PCG support the speculation (from one of my threads here) that "pcg_setseq_128_xsl_rr_64_random_r" behaves/would behave as a 'low-discrepancy sequence'?

My method of meta-analysis is still a work-in-progress, so just looking for confirmation and/or clarification of terminology.

Thanks,

Chris

[Sebastiano Vigna]

On May 15, 2018 8:06:57 PM EDT, Chris Rutz <rut...@gmail.com> wrote:
>Does your analysis of PCG support the speculation (from one of my
>threads
>here) that "pcg_setseq_128_xsl_rr_64_random_r" behaves/would behave as
>a
>'low-discrepancy sequence'?

No, I don't think that's true. But I'm no expert...
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

[Chris Rutz]

On Tuesday, May 15, 2018 at 9:21:40 PM UTC-4, Sebastiano Vigna wrote:

On May 15, 2018 8:06:57 PM EDT, Chris Rutz <rut...@gmail.com> wrote:
>Does your analysis of PCG support the speculation (from one of my
>threads
>here) that "pcg_setseq_128_xsl_rr_64_random_r" behaves/would behave as
>a
>'low-discrepancy sequence'?

No,  I don't think that's true.  But I'm no expert...

  

Thanks... not sure if would change your opinion, but I should have clarified: "... behave as a 'low-discrepancy sequence' with respect to certain classes of statistical tests?"

[Sebastiano Vigna]

> On 15 Sep 2018, at 07:36, ivo....@gmail.com wrote:
>
> I'm sorry, but this is simply ridiculous.

I'm really, really sorry (I hate to do this), but you have to face reality: you have no understanding whatsoever of the very basic ideas of the field, and your post is just noise.

> The "multiplications Melissa O'Neill used in her criticism of xoshiro256**" were multiplying the generator's output by a number. Yes, it is a number (any number) with the low-order byte being 57, which happens to undo the scrambling just enough to make the result catastrophically fail. As she says:

"Catastrophically fail" for a few bits with linear artifacts after a specific bijection is entirely ridiculous. The Python generator has linear artifacts in all bits. The gcc generator has linear artifacts in all bits. You're claiming that the world is crumbling around us, with everybody using generators that "catastrophically fail". The gap test--that's a catastrophy. The matrix rank test is just something that's nice to get rid of (and we do).

I can suggest you some basic readings on the subject.

> This generator, usually called pcg64_once_insecure is designed for very specific use cases.

You're again confusing "insecure" and "passing strong statistical tests", showing, once more, that you do not understand the basic ideas in the field.

Please do not post anymore here, I'm trying to keep the ratio sound/noise reasonable.

Ciao,

seba

[k.grocho...@gmail.com]

There's a response to it: http://www.pcg-random.org/posts/on-vignas-pcg-critique.html

And this response is honestly terrible. xoshiro256** has a 2²⁵⁶-1 period usable for large scale parallelism due to its 3-dimensional stream system (long-jump, jump and next) with each of the dimensions having great length. This parallel stream system cannot exist with any PCG generator.

[k.grocho...@gmail.com]

btw I'm terriblifying M.E. O'Neill's response, not yours.

[Sebastiano Vigna]

On June 11, 2019 9:35:06 PM GMT+03:00, k.grocho...@gmail.com wrote:
>On Monday, 14 May 2018 13:37:55 UTC+2, Sebastiano Vigna wrote:
>> For those who might be interested, I put together a review of PCG
>generators.
>>
>> http://pcg.di.unimi.it/pcg.php
>>
>> It gather a few sparse comments I made in discussions here and
>elsewhere.
>>
>> Ciao,
>>
>> seba
>
>There's a response to it:
>http://www.pcg-random.org/posts/on-vignas-pcg-critique.html

Oh I guess there must be something. There's always something. But I'm really tired of her crap.

There's a good reason we got rid of LCG with power-of-2 moduli. They can be used, of course, but you must be very careful.

--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

--
Il tuo 5 x mille progetti
Sostieni la ricerca, investi sul futuro dei giovani
Universita` degli Studi di Milano - codice fiscale 80012650158

[k.grocho...@gmail.com]

There's also this page http://www.pcg-random.org/posts/xoshiro-repeat-flaws.html about flaws in "zeroland states" in xoshiro256**, showing various probability numbers much smaller than 2^-256. This is ridiculous; I don't think any statistical test is able to detect that (with proper SplitMix seeding, not some arbitrarily constructed seeds).

[Sebastiano Vigna]

> On 12 Jun 2019, at 08:55, k.grocho...@gmail.com wrote:
>
> There's also this page http://www.pcg-random.org/posts/xoshiro-repeat-flaws.html about flaws in "zeroland states" in xoshiro256**, showing various probability numbers much smaller than 2^-256. This is ridiculous; I don't think any statistical test is able to detect that (with proper SplitMix seeding, not some arbitrarily constructed seeds).

🤷🏻‍♂️

Ciao,

seba

[k.grocho...@gmail.com]

And there's also this article http://www.pcg-random.org/posts/xoroshiro-fails-truncated.html that claims xoroshiro128+ fails PractRand even with only the top 32 bits. What does this mean and how does it relate to your claim of passing statistical tests except for the lowest 4 bits (0 to 15)?

[Sebastiano Vigna]

> On 12 Jun 2019, at 10:33, k.grocho...@gmail.com wrote:
>
> And there's also this article http://www.pcg-random.org/posts/xoroshiro-fails-truncated.html that claims xoroshiro128+ fails PractRand even with only the top 32 bits. What does this mean and how does it relate to your claim of passing statistical tests except for the lowest 4 bits (0 to 15)?

It does not even pass our Hamming-weight dependencies test, and our test fails *before* PractRand (it's a stronger test). It's written clearly on the web page (and in the paper):

"If you are tight on space, xoroshiro128** (XOR/rotate/shift/rotate) and xoroshiro128+ have the same speed and use half of the space; the same comments apply. They are suitable only for low-scale parallel applications; moreover, xoroshiro128+ exhibits a mild dependency in Hamming weights that generates a failure after 5 TB of output in our test. We believe this slight bias cannot affect any application."

The point I make about the low bits is about *linear dependencies*, which, indeed, do not appear even after 5PB of testing. It is a generic comment that applies to all "+" generators. "+" is fast and easy, but leaves the lower bits of low linear complexity as the carry chains are too short.

All the tests in PractRand that are failed are variants of Hamming weights--they're all dependent. No surprise.

Really, this lady should get a life. 😂

[k.grocho...@gmail.com]

This page http://www.pcg-random.org/posts/visualizing-the-heart-of-some-prngs.html appears to demonstrate how xoroshiro+ is worse than PCG on a small scale. But no mention of * or ** on there. I mean, you even made the deliberate choice to use * instead of + in xoroshiro64* and you used different parameters for ** in xoroshiro64**, due to the properties of small scale.

http://www.pcg-random.org/posts/other-good-options.html is a list of "good generators" but it excludes xoroshiro128+ and xorshift128+ as the ending shows. Yet it makes no mention of xoroshiro128** or xoshiro256** at all.

[k.grocho...@gmail.com]

And there's also http://www.pcg-random.org/posts/too-big-to-fail.html which demonstrates how generators of at least 96 bits of state are "too big to fail".

However the thing is, xoroshiro/xoshiro doesn't follow a strict straight structure from 1024 bits all the way down to 64. It "curves" right at the bottom with + replaced by *, and ** replaced by a hybrid of * and **. So all of the generators are nearly equally statistically good, with the extra state space providing advantages for not statistical quality, but parallelism. On the other hand, the PCG structure gets exponentially better statistically with the state space, but to do so it takes increasingly big multiplications, with the public PCG releases maxing out the multiplications at 128 bits and instead using "ext" to go further, which isn't any good for parallelism.

[k.grocho...@gmail.com]

Someone at https://www.freebasic.net/forum/viewtopic.php?t=26842 claims xoshiro256** fails PractRand.

"xoshiro256** failed spectacularly within a few seconds with more FAIL!!!!!!!! than you can shake a stick at. FAIL!!!!!!!! is the worst failure PractRand reports with p values of zero. I spent some time going through my code and could not find anything wrong. So, I looked at xoroshiro128**. That went down the tubes as well."

[Sebastiano Vigna]

> On 24 Jun 2019, at 10:04, k.grocho...@gmail.com wrote:
>
> Someone at https://www.freebasic.net/forum/viewtopic.php?t=26842 claims xoshiro256** fails PractRand.
>
> "xoshiro256** failed spectacularly within a few seconds with more FAIL!!!!!!!! than you can shake a stick at. FAIL!!!!!!!! is the worst failure PractRand reports with p values of zero. I spent some time going through my code and could not find anything wrong. So, I looked at xoroshiro128**. That went down the tubes as well."

Yes, chemtrails, reptilians, etc.

[k.grocho...@gmail.com]

You mean that chemtrails, reptilians, etc. are names of tests that xoshiro256** fails?

[Sebastiano Vigna]

> On 24 Jun 2019, at 14:27, k.grocho...@gmail.com wrote:
>
>
> You mean that chemtrails, reptilians, etc. are names of tests that xoshiro256** fails?

🤦🏻‍♂️

[k.grocho...@gmail.com]

> >
> >
> > You mean that chemtrails, reptilians, etc. are names of tests that xoshiro256** fails?
>
> 🤦🏻‍♂️
>
> Ciao,
>
> seba
>
>
> --
> Il tuo 5 x mille progetti
> Sostieni la ricerca, investi sul futuro dei giovani
> Universita` degli Studi di Milano - codice fiscale 80012650158

?

You should edit the source code comments so that it is

> /* This is xoshiro256** 1.0, our all-purpose, rock-solid generator. It has
> excellent (sub-ns) speed, a state (256 bits) that is large enough for
> any parallel application, and it passes all tests we are aware of
> (except for chemtrails, reptilians, etc.).
>
> For generating just floating-point numbers, xoshiro256+ is even faster.
>
> The state must be seeded so that it is not everywhere zero. If you have
> a 64-bit seed, we suggest to seed a splitmix64 generator and use its
> output to fill s. */

[david.j...@gmail.com]

On Monday, 24 June 2019 18:04:09 UTC+10, k.groch...@gmail.com wrote:
> Someone at https://www.freebasic.net/forum/viewtopic.php?t=26842 claims xoshiro256** fails PractRand.
>
> "xoshiro256** failed spectacularly within a few seconds with more FAIL!!!!!!!!

It worked ok for me. I wonder if his implementation in freebasic was incorrect somehow? I don't think he posted his source code, so it's hard to check.

[k.grocho...@gmail.com]

So, you used PractRand on xoshiro256** and resulted in something like this:

rng=RNG_stdin64, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 411 seconds
Test Name Raw Processed Evaluation
chemtrails R= +22.5 p = 0 FAIL!!!!!!!!
reptilians R=+374.9 p = 0 FAIL!!!!!!!!
reptilians R=+296.4 p = 0 FAIL!!!!!!!!
chemtrails R= +85.3 p = 0 FAIL!!!!!!!!
...and 1637 test result(s) without anomalies

[david.j...@gmail.com]

On Thursday, 4 July 2019 17:54:33 UTC+10, k.groch...@gmail.com wrote:

> So, you used PractRand on xoshiro256** and resulted in something like this:

Testing Xoshiro256**

Here is the seed method used. This is just what happened to be lying around
on my home machine. Hope it's the official method.

void seed(Uint64 s) {
int j;
Uint64 z;

for (j=0; j<4; j++)
{
z = ( s += 0x9E3779B97F4A7C15ULL );
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
ranst[j] = z;
}
}

I'm pretty sure i did Practrand to 256GB at one stage and everything was ok.
Prof. Vigna may have gone much further. I mostly concentrated on other tests.
Practrand is a good one though, and if you want to get serious about prngs,
Practrand should be in your toolkit.

$ ./RNG_test xoshiro256 -seed 42 -tlmin 16GB -tlmax 16GB
RNG_test using PractRand version 0.94
RNG = xoshiro256, seed = 0x42
test set = core, folding = standard (64 bit)

rng=xoshiro256, seed=0x42
length= 16 gigabytes (2^34 bytes), time= 509 seconds
no anomalies in 310 test result(s)

$ ./RNG_test xoshiro256 -seed 43 -tlmin 64GB -tlmax 64GB
RNG_test using PractRand version 0.94
RNG = xoshiro256, seed = 0x43
test set = core, folding = standard (64 bit)

rng=xoshiro256, seed=0x43
length= 64 gigabytes (2^36 bytes), time= 2053 seconds
no anomalies in 340 test result(s)

[piotrun...@wp.pl]

The point of xoshiro256**, etc. is not to have an acceptable randomness quality for its state size, but an acceptable randomness quality for its speed. Obviously a generator that passes some complex tests with a bare minimum of, say, 82 bits but takes 100 seconds per random number isn't as general-purpose as xoshiro256**.

[auihnci...@gmail.com]

Seriously. Deleting the previous 2 messages. Why are you doing this?