PCG XSL-RR-RR failed in PractRand or am I doing something wrong?

[osobli...@gmail.com]

I'm testing XSL-RR-RR generator in PractRand, but it fails after 1 gigabyte:

RNG_test using PractRand version 0.95
RNG = RNG_stdin, seed = unknown
test set = core, folding = standard(unknown format)

rng=RNG_stdin, seed=unknown
length= 32 megabytes (2^25 bytes), time= 3.9 seconds
no anomalies in 169 test result(s)

rng=RNG_stdin, seed=unknown
length= 64 megabytes (2^26 bytes), time= 9.2 seconds
no anomalies in 182 test result(s)

rng=RNG_stdin, seed=unknown
length= 128 megabytes (2^27 bytes), time= 18.4 seconds
no anomalies in 199 test result(s)

rng=RNG_stdin, seed=unknown
length= 256 megabytes (2^28 bytes), time= 35.4 seconds
no anomalies in 217 test result(s)

rng=RNG_stdin, seed=unknown
length= 512 megabytes (2^29 bytes), time= 71.5 seconds
Test Name Raw Processed Evaluation
[Low1/32]FPF-14+6/16:cross R= +9.4 p = 7.1e-8 very suspicious
...and 231 test result(s) without anomalies

rng=RNG_stdin, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 138 seconds
Test Name Raw Processed Evaluation
[Low1/32]FPF-14+6/16:cross R= +14.1 p = 1.3e-11 FAIL
...and 250 test result(s) without anomalies

This is my code in Python:

https://pastebin.com/UquDZz9j

I'm using 47026247687942121848144207491837523525 multiplier in 128-bit underlying LCG, so it could be fine. Also I don't think so I made any mistake in PCGmixer (XSL-RR-RR):

https://en.wikipedia.org/wiki/Permuted_congruential_generator

So why is it failing tests? Can anyone check my results? Maybe I used wrong increment? Or maybe it doesn't pass the tests? According to the paper:

https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf

It should. Or not? There is no information in it that the author tested this generator (but I think she did it for sure). After all, I think I'm doing something wrong.

[Leo]

On Fri, 03 Sep 2021 15:18:26 -0700, osobli...@gmail.com wrote:

> I'm testing XSL-RR-RR generator in PractRand, but it fails after 1
> gigabyte:
>

> This is my code in Python:
>
> https://pastebin.com/UquDZz9j
>
> I'm using 47026247687942121848144207491837523525 multiplier in 128-bit
> underlying LCG, so it could be fine. Also I don't think so I made any
> mistake in PCGmixer (XSL-RR-RR):
>
> https://en.wikipedia.org/wiki/Permuted_congruential_generator
>
> So why is it failing tests? Can anyone check my results? Maybe I used
> wrong increment? Or maybe it doesn't pass the tests? According to the
> paper:
>
> https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
>
> It should. Or not? There is no information in it that the author tested
> this generator (but I think she did it for sure). After all, I think I'm
> doing something wrong.

It looks like you are outputting the whole state, can you try
outputting half of it instead?

Usually with these kinds of generators you need to keep some of the
state hidden to pass the RNG tests. Of course, that comes with a speed
penalty so you need to play around with how much you output.

--
Leo

[osobli...@gmail.com]

sobota, 4 września 2021 o 13:12:40 UTC+2 Leo napisał(a):
> On Fri, 03 Sep 2021 15:18:26 -0700, osobli...@gmail.com wrote:
>
> > I'm testing XSL-RR-RR generator in PractRand, but it fails after 1
> > gigabyte:
> >
> > This is my code in Python:
> >
> > https://pastebin.com/UquDZz9j
> >
> > I'm using 47026247687942121848144207491837523525 multiplier in 128-bit
> > underlying LCG, so it could be fine. Also I don't think so I made any
> > mistake in PCGmixer (XSL-RR-RR):
> >
> > https://en.wikipedia.org/wiki/Permuted_congruential_generator
> >
> > So why is it failing tests? Can anyone check my results? Maybe I used
> > wrong increment? Or maybe it doesn't pass the tests? According to the
> > paper:
> >
> > https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf
> >
> > It should. Or not? There is no information in it that the author tested
> > this generator (but I think she did it for sure). After all, I think I'm
> > doing something wrong.
> It looks like you are outputting the whole state, can you try
> outputting half of it instead?

I can't because it is not a definition of XSL-RR-RR. It turns 128 bits of state into 128 bits of output.

[osobli...@gmail.com]

By the way it was invented in 2014. Back then, there were no PractRand tests, which are probably one of the most demanding tests on the market.

Definition of XSL-RR-RR mixer:

1. Take 128-bit number from underlying LCG and extract 6 most significant bits:

count = x >> 122

2. Compute low 64 bits. First XOR most significant 64 bits of number x with least significant 64 bits of number x (all modulo 2**64). Then rotate it right by count.

low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)

3. Compute high 64 bits. Take most significant 64 bits of number x and rotate it right by low64 & 63.

high64 = rotr64((uint64_t)(x >> 64), low64 & 63);

4. Result is high64 << 64 bitwise OR with low64:

high64 << 64 | low64

[osobli...@gmail.com]

I fixed it by xoring consecutive outputs. Python code:

import struct
import sys

x = 83866140117348733064738400095399246193
#seed

def PCGmixer(x):
count1 = x >> 122
x1 = (x ^ (x >> 64)) & 18446744073709551615
low64 = (x1 >> count1) | (x1 << (64 - count1)) & 18446744073709551615
x2 = (x >> 64) & 18446744073709551615
count2 = low64 & 63
high64 = (x2 >> count2) | (x2 << (64 - count2)) & 18446744073709551615
x = (high64 << 64) | low64
return x

def LCG(x):
x = (x * 47026247687942121848144207491837523525 + 83866140218348733064834828227924511723) & 340282366920938463463374607431768211455
return x

w=0
while 1 == 1:

w_1 = w

x=LCG(x)
w=PCGmixer(x)

w_2 = w_1 ^ w


split = [(w_2 >> x) & 0xFFFFFFFF for x in reversed(range(0, 128, 32))]
binary = struct.pack('IIII', split[0], split[1], split[2], split[3])
sys.stdout.buffer.write(binary)
#splitting required by PractRand

So we generate output_1, output_2, output_3, output_4, ... and our numbers are:

output_1 ^ output_2

output_2 ^ output_3

output_3 ^ output_4

and so on. For now it passes more tests:

RNG_test using PractRand version 0.95
RNG = RNG_stdin, seed = unknown
test set = core, folding = standard(unknown format)

rng=RNG_stdin, seed=unknown

length= 16 megabytes (2^24 bytes), time= 2.1 seconds
no anomalies in 153 test result(s)

rng=RNG_stdin, seed=unknown
length= 32 megabytes (2^25 bytes), time= 5.6 seconds

no anomalies in 169 test result(s)

rng=RNG_stdin, seed=unknown

length= 64 megabytes (2^26 bytes), time= 11.1 seconds

no anomalies in 182 test result(s)

rng=RNG_stdin, seed=unknown

length= 128 megabytes (2^27 bytes), time= 20.7 seconds

no anomalies in 199 test result(s)

rng=RNG_stdin, seed=unknown

length= 256 megabytes (2^28 bytes), time= 38.5 seconds

no anomalies in 217 test result(s)

rng=RNG_stdin, seed=unknown

length= 512 megabytes (2^29 bytes), time= 72.8 seconds
no anomalies in 232 test result(s)

rng=RNG_stdin, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 141 seconds
no anomalies in 251 test result(s)

rng=RNG_stdin, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 275 seconds
no anomalies in 269 test result(s)

rng=RNG_stdin, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 560 seconds
no anomalies in 283 test result(s)

rng=RNG_stdin, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 1096 seconds

Test Name Raw Processed Evaluation

[Low1/8]DC6-9x1Bytes-1 R= +5.8 p = 3.5e-3 unusual
...and 299 test result(s) without anomalies

rng=RNG_stdin, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 2189 seconds
no anomalies in 315 test result(s)

rng=RNG_stdin, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 4366 seconds
no anomalies in 328 test result(s)

rng=RNG_stdin, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 8809 seconds

no anomalies in 344 test result(s)

rng=RNG_stdin, seed=unknown

length= 128 gigabytes (2^37 bytes), time= 17252 seconds
no anomalies in 359 test result(s)

rng=RNG_stdin, seed=unknown
length= 256 gigabytes (2^38 bytes), time= 34723 seconds
no anomalies in 372 test result(s)

rng=RNG_stdin, seed=unknown
length= 512 gigabytes (2^39 bytes), time= 69312 seconds
no anomalies in 387 test result(s)

I'll see if it fails.