The wrap-up on PCG generators

401 views
Skip to first unread message

Sebastiano Vigna

unread,
May 14, 2018, 7:37:55 AM5/14/18
to prng
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

Message has been deleted

albert...@yahoo.com

unread,
May 14, 2018, 10:58:55 PM5/14/18
to prng
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

unread,
May 14, 2018, 11:24:31 PM5/14/18
to prng
> 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

unread,
May 15, 2018, 8:06:57 PM5/15/18
to prng
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

unread,
May 15, 2018, 9:21:40 PM5/15/18
to Chris Rutz, prng


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

unread,
May 15, 2018, 11:02:20 PM5/15/18
to prng


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?"
Message has been deleted

Sebastiano Vigna

unread,
Sep 15, 2018, 4:26:25 AM9/15/18
to ivo....@gmail.com, prng

> 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

unread,
Jun 11, 2019, 2:35:06 PM6/11/19
to prng
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

unread,
Jun 11, 2019, 2:38:02 PM6/11/19
to prng
btw I'm terriblifying M.E. O'Neill's response, not yours.

Sebastiano Vigna

unread,
Jun 11, 2019, 3:07:53 PM6/11/19
to pr...@googlegroups.com


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

unread,
Jun 12, 2019, 1:55:51 AM6/12/19
to prng
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

unread,
Jun 12, 2019, 2:54:17 AM6/12/19
to prng


> 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

unread,
Jun 12, 2019, 3:33:08 AM6/12/19
to prng
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

unread,
Jun 12, 2019, 3:44:38 AM6/12/19
to prng


> 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

unread,
Jun 12, 2019, 4:14:13 AM6/12/19
to prng
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

unread,
Jun 14, 2019, 12:18:11 PM6/14/19
to prng
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

unread,
Jun 24, 2019, 4:04:09 AM6/24/19
to prng
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

unread,
Jun 24, 2019, 4:09:50 AM6/24/19
to prng


> 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

unread,
Jun 24, 2019, 8:27:35 AM6/24/19
to prng

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

Sebastiano Vigna

unread,
Jun 24, 2019, 8:42:57 AM6/24/19
to pr...@googlegroups.com


> 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

unread,
Jun 24, 2019, 12:02:08 PM6/24/19
to prng

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

unread,
Jun 25, 2019, 1:28:12 AM6/25/19
to prng
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

unread,
Jul 4, 2019, 3:54:33 AM7/4/19
to prng

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

unread,
Jul 7, 2019, 10:58:29 PM7/7/19
to prng
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

unread,
Nov 2, 2019, 6:53:37 AM11/2/19
to prng
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**.
Message has been deleted
Message has been deleted

auihnci...@gmail.com

unread,
Nov 2, 2019, 2:08:31 PM11/2/19
to prng
Seriously. Deleting the previous 2 messages. Why are you doing this?
Reply all
Reply to author
Forward
0 new messages