More PractRand Passes: ChaCha & Truncated XorShift*

Continuing my recent burst of PRNG testing with PractRand, here are a few more passes, this time for the generators I mentioned in my post on reasonable alternatives to PCG.

• ChaCha<3>
• ChaCha<4>
• XorShift* 64/32 (i.e., high 32 bits of 64-bit XorShift*)
• XorShift* 128/64 (i.e., high 64 bits of 128-bit XorShift*)

None of these results should be a surprise. In the PCG paper, I looked at truncated XorShift* generators and onserved that they passed TestU01 with plenty of headroom. Nevetheless, it's nice to confirm.

Also, none of these generators are trivially predictable (but obviously the smaller XorShift versions can be fairly quickly brute forced). ChaCha obviously has much stronger prediction difficulty, given that with more rounds it is considered cryptographically secure. When simply trying to protect against algorithmic complexity attacks, I think four rounds is fine.

Testing ChaCha

I used Orson Peters's implementation.

ChaCha<1> and ChaCha<2>

Without enough rounds, ChaCha fails statistical tests badly. Don't use these ones.

ChaCha<3> ¹

linux$ ./chacha.3 | ./RNG_test.new stdin32
ChaCha<3>(0x0daf885421137063,0xf476e1c71263aa18) initialized.
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x33ed287e
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x33ed287e
length= 128 megabytes (2^27 bytes), time= 2.8 seconds
  no anomalies in 117 test result(s)

[...]

rng=RNG_stdin32, seed=0x33ed287e
length= 8 terabytes (2^43 bytes), time= 166331 seconds
  no anomalies in 244 test result(s)

rng=RNG_stdin32, seed=0x33ed287e
length= 16 terabytes (2^44 bytes), time= 340113 seconds
  no anomalies in 252 test result(s)

rng=RNG_stdin32, seed=0x33ed287e
length= 32 terabytes (2^45 bytes), time= 684283 seconds
  no anomalies in 260 test result(s)

Looks good all the way out to 32 TB!

ChaCha<4>

linux$ ./chacha.4 | ./RNG_test stdin32
ChaCha<4>(0x422327c44b169678,0xe785ae07c0439891) initialized.
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0xc9e6f300
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0xc9e6f300
length= 128 megabytes (2^27 bytes), time= 2.4 seconds
  no anomalies in 117 test result(s)

rng=RNG_stdin32, seed=0xc9e6f300
length= 256 megabytes (2^28 bytes), time= 5.3 seconds
  no anomalies in 124 test result(s)

[...]

rng=RNG_stdin32, seed=0xc9e6f300
length= 8 terabytes (2^43 bytes), time= 166219 seconds
  no anomalies in 244 test result(s)

rng=RNG_stdin32, seed=0xc9e6f300 
length= 16 terabytes (2^44 bytes), time= 332149 seconds 
  no anomalies in 252 test result(s)

rng=RNG_stdin32, seed=0xc9e6f300 
length= 32 terabytes (2^45 bytes), time= 664913 seconds 
  no anomalies in 260 test result(s)

Also looks good (unsurprising since ChaCha<3> passed).

Truncated XorShift*

XorShift* generators are widely known, and back in 2014, I considered them the main competition for PCG. Other implementations exist, no doubt, but for fun I wrote my own; you can find my C++ implementation as a Github gist here.

Since I was doing the math to find suitable shift parameters and multipliers, I figured “why do one when you can do four”, so the code provides for distinct (and hopefully statistically independent) generators at each size. Of course that gives more to test.

XorShift* 64/32

I'm starting to move to mutltithreaded testing to get things done faster.

linux$ ./xorshift64star32a | ./RNG_test stdin32 -multithreaded
xorshift64star32a(0xee472e19cf5b5c8c) initialized.
RNG_test using PractRand version 0.93
RNG = RNG_stdin32, seed = 0x1a9bd1f6
test set = normal, folding = standard (32 bit)

rng=RNG_stdin32, seed=0x1a9bd1f6
length= 256 megabytes (2^28 bytes), time= 2.3 seconds
  no anomalies in 124 test result(s)

rng=RNG_stdin32, seed=0x1a9bd1f6
length= 512 megabytes (2^29 bytes), time= 4.8 seconds
  no anomalies in 132 test result(s)

[...]

rng=RNG_stdin32, seed=0x1a9bd1f6
length= 8 terabytes (2^43 bytes), time= 53722 seconds
  no anomalies in 244 test result(s)

rng=RNG_stdin32, seed=0x1a9bd1f6
length= 16 terabytes (2^44 bytes), time= 107537 seconds
  no anomalies in 252 test result(s)

rng=RNG_stdin32, seed=0x1a9bd1f6
length= 32 terabytes (2^45 bytes), time= 215209 seconds
  no anomalies in 260 test result(s)

Passes all the way out to 32 TB. So do the other three versions.

XorShift* 128/64

The tests for these four are only up to 16 TB at this point, but since their smaller siblings did great, I don't see any likelihood of problems. Here are the results so far for xorshift128star64a:

$linux ./xorshift128star64a | time ./RNG_test stdin64 -multithreaded
xorshift128star64a(0xeae02e72a9af2d09) initialized.
RNG_test using PractRand version 0.93
RNG = RNG_stdin64, seed = 0xc7577148
test set = normal, folding = standard (64 bit)

rng=RNG_stdin64, seed=0xc7577148
length= 256 megabytes (2^28 bytes), time= 2.2 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low4/64]BCFN(2+1,13-5,T)         R=  -6.2  p =1-8.9e-4   unusual
  ...and 158 test result(s) without anomalies

rng=RNG_stdin64, seed=0xc7577148
length= 512 megabytes (2^29 bytes), time= 4.8 seconds
  no anomalies in 169 test result(s)

rng=RNG_stdin64, seed=0xc7577148
length= 1 gigabyte (2^30 bytes), time= 9.3 seconds
  no anomalies in 180 test result(s)

[...]

rng=RNG_stdin64, seed=0xc7577148
length= 4 terabytes (2^42 bytes), time= 27422 seconds
  no anomalies in 308 test result(s)

rng=RNG_stdin64, seed=0xc7577148
length= 8 terabytes (2^43 bytes), time= 54853 seconds
  no anomalies in 319 test result(s)

rng=RNG_stdin64, seed=0xc7577148
length= 16 terabytes (2^44 bytes), time= 109397 seconds
  no anomalies in 329 test result(s)

I'll update this post when the test finishes.