PRNG performance with TestU01 or PractRand

[TheIronBorn]

mum-prng passes NIST STS but that's not the state-of-the-art for PRNG testing.

Do you have info on the performance of mum-prng in TestU01 or PractRand? PractRand is probably the more convenient of the two.

[vnmakarov]

Sorry, I don't have the info. I looked at TestU01 long time ago but the interface was so complicated so I gave up. Thank you for PractRand reference. I am going to try mum-prng on it when I have more time. If it does not pass, I probably could make the PRNG passes them but by slowing down the algorithm.

[TheIronBorn]

I'd be interested to see what sort of changes that would require.

[vnmakarov]

I'd be interested to see what sort of changes that would require.

It would require more hashing.

I've just finished testing the PRNGs by PractRand (by .. | RNG_test stdin64).

As expected XOROSHIRO+ and RAND failed instantly. BBS failed too which is strange as the hash function on which it is built is a crypto-level hash function.

CHACHA and SIP24 passed w/o problems as it should be because they are built on proven different crypto-level hash functions. MUM512 has no problems too. I position MUM512 as a crypto-level function although nobody tried to break it or did a crypto-analysis of it.

MUM has no problems too. RNG_test reported 8GB input data consumed.

But those are preliminary results as RNG_test crashes with sigfault probably at the end of its work. I need to learn PractRand more to be sure that I used it correctly.

[vnmakarov]

MUM has no problems too. RNG_test reported 8GB input data consumed.

Sorry, it was actually 16GB.

[TheIronBorn]

You may want to replace your xoroshiro128+ comparison with the newer xoroshiro128** or xoshiro256** as they obsoleted xoroshiro128+: http://xoshiro.di.unimi.it.

[vnmakarov]

You may want to replace your xoroshiro128+ comparison with the newer xoroshiro128** or xoshiro256** as they obsoleted xoroshiro128+

Thanks for mentioning the new versions of xoroshiro/xoshiro. I've tried xoroshiro128{,++}, xoshiro256{,++), xoshiro512{**,++}. They all failed PractRand in just a few seconds.

Although the fastest one xoshiro256+ is about 20% faster than MUM-PRNG.

Probably this month, I will update the benchmark script and add a test script using PractRand. Thank you, your issue was useful.

[TheIronBorn]

What specifications did you use for ++ generators? I believe the paper only mentions specifications for a xoroshiro32++ generator.

[TheIronBorn]

Also something went wrong with formatting so I can't quite tell if you tested the ** generators but they should do much better in PractRand

[vnmakarov]

Also something went wrong with formatting so I can't quite tell if you tested the ** generators but they should do much better in PractRand

I think stars were treated as markdown bold markers. Yes, I've tried all star versions too. For example, this is a part of PractRand output for xoshiro256**:

RNG_test using PractRand version 0.93                                                                                                                  
RNG = RNG_stdin64, seed = 0x7af8503                                                                                                                    
test set = normal, folding = standard (64 bit)                                                                                                         
                                                                                                                                                       
rng=RNG_stdin64, seed=0x7af8503                                                                                                                        
length= 256 megabytes (2^28 bytes), time= 2.9 seconds                                                                                                  
  Test Name                         Raw       Processed     Evaluation                                                                                 
  BCFN(2+0,13-2,T)                  R=+27538479 p = 0           FAIL !!!!!!!!                                                                          
  BCFN(2+1,13-2,T)                  R=+13016562 p = 0           FAIL !!!!!!!!                                                                          
  BCFN(2+2,13-3,T)                  R=+8037376 p = 0           FAIL !!!!!!!!                                                                           
  BCFN(2+3,13-3,T)                  R=+3903883 p = 0           FAIL !!!!!!!!                                                                           
  BCFN(2+4,13-3,T)                  R=+1911999 p = 0           FAIL !!!!!!!!                                                                           
  BCFN(2+5,13-4,T)                  R=+1199616 p = 0           FAIL !!!!!!!!                                                                           
  BCFN(2+6,13-5,T)                  R=+746903 p = 0           FAIL !!!!!!!!                                                                            
  BCFN(2+7,13-5,T)                  R=+370686 p = 0           FAIL !!!!!!!!                                                                            
  BCFN(2+8,13-6,T)                  R=+228593 p = 0           FAIL !!!!!!!!                                                                            
  BCFN(2+9,13-6,T)                  R=+113862 p = 0           FAIL !!!!!!!!                                                                            
  BCFN(2+10,13-7,T)                 R=+69095  p = 0           FAIL !!!!!!!!                                                                            
  BCFN(2+11,13-8,T)                 R=+40957  p = 0           FAIL !!!!!!!!                                                                            
  BCFN(2+12,13-8,T)                 R=+20441  p =  1e-5188    FAIL !!!!!!!!                                                                            
  BCFN(2+13,13-9,T)                 R=+11734  p =  8e-2638    FAIL !!!!!!!!                                                                            
  BCFN(2+14,13-9,T)                 R= +5853  p =  3e-1316    FAIL !!!!!!!!                                                                            
  DC6-9x1Bytes-1                    R=+21446369 p = 0           FAIL !!!!!!!!                                                                          
  Gap-16:A                          R=+6683990 p = 0           FAIL !!!!!!!!                                                                           
  Gap-16:B                          R=+26208543 p = 0           FAIL !!!!!!!!                                                                          
  FPF-14+6/16:cross                 R=+602920393 p = 0           FAIL !!!!!!!!                                                                         
  BRank(12):128(4)                  R= +5300  p~=  1e-2819    FAIL !!!!!!!!                                                                            
  BRank(12):256(4)                  R=+10811  p~=  1e-5750    FAIL !!!!!!!!                                                                            
  BRank(12):384(1)                  R= +8161  p~=  1e-2457    FAIL !!!!!!!!                                                                            
  BRank(12):512(2)                  R=+15438  p~=  2e-4648    FAIL !!!!!!!!                                                                            
  BRank(12):768(1)                  R=+16427  p~=  3e-4946    FAIL !!!!!!!!                                                                            
  BRank(12):1K(2)                   R=+31025  p~=  1e-9340    FAIL !!!!!!!!                                                                            
  BRank(12):1536(1)                 R=+32960  p~=  4e-9923    FAIL !!!!!!!! 
  ...

[TheIronBorn]

That's odd, my testing has it >16GB Edit: >512GB.

[vnmakarov]

That's odd, my testing has it >16GB Edit: >512GB.

Sorry, I did not set up the seed as it was recommended. After setting the seed all starstar versions passed 4TB stream. I stopped after that. All plus versions failed in a second or two.

[vnmakarov]

I've added all xoshiro/xoroshiro version results for comparison with other PRNGs. The results were obtained on a modern processor i7-8700K. I hope they will be interesting for you.

[lemire]

@vnmakarov

I have added your RNG under the name "wyhash" with the particular wyhash implementation at...
https://github.com/lemire/testingRNG

It passes Big Crush in my tests. (I have instrumented L'Ecuyer's testu01 so that it is usable.)

Well, I am 95% certain that what I present as wyhash (that's the name I found it under) is basically equivalent to your MUM generator... but I admit that I did not dig into your source code too closely.

You may be interested in the following blog post: The fastest conventional random number generator that can pass Big Crush? I describe my implementation in simple terms. I'd be interested in your feedback to see whether I am right to think that wyhash is equivalent to your generator.

Further reading: Lemire and O’Neill, Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity, Computational and Applied Mathematics 350, 2019

[vnmakarov]

Yes, wayhash looks exactly like MUM-primitive. The issue is that whyhash is not portable. First of all not all GCC targets support 128 arithmetic. So you need to implement 128-bit arithmetic with 64-bit arithmetic. Also on some GCC targets (e.g. aarch64) 128-bit multiplication is slow. You could get faster implementation by using GCC asm extension.

As for mum-prng itself, it has a bigger state (1024-bit) and it is updated through the MUM-primitive.

[lemire]

@vnmakarov Thanks.

Coincidentally, I just published the following post: ARM and Intel have different performance characteristics: a case study in random number generation.