Introduction

This page reports results of the Hamming-weight dependency test described in our paper. It is a very strong test, looking for dependencies between the number of zeroes and ones in consecutive outputs, and it is engineered to the point that it can be practically run on petabytes of data (given that the generator is fast enough).

Besides find bias in our own generators, such as xorshift128+, we were able to find some new, unknown bias in previous generators such as some versions of the Mersenne Twister and the Tiny Mersenne Twister, for which no tests other than linearity were known to fail. Note that xorshift128+ fails the test after 6 GB of output, but the SIMD-oriented Fast Mersenne Twister (607 bits) fails after much less output. xoroshiro128+ needs four orders of magnitude more data, and the other generators we propose show no sign of bias after a petabyte (1015 bytes) of output.

Results

To understand fully the columns of this table, we suggest to have a look at the description of the test in the paper. The third column shows the amount of output that has to be processed to obtain a p-value below 10-20. Note that the Mersenne Twister sports multiple values, as we tested multiple possible parameters using the dcmt library. Analogously, we tested several parameters of the Tiny Mersenne Twister.

PRNG w Period p = 10−20 @ Faulty signature
xorshift128+ 64 2128 − 16 × 109 00000021
xoroshiro128+64 2128 − 15 × 1012 00000012
Tiny Mersenne Twister (64 bits) 32 2127 − 18 × 101310001021
Tiny Mersenne Twister (32 bits) 32 2127 − 14 × 101310001021
SFMT (607 bits) 32 2607 − 14 × 108 001000001000
dSFMT (521 bits) 32 2521 − 16 × 1012 1001000100100010
Mersenne Twister (521 bits) 32 2521 − 14 × 10101000000100000000, 2000000100000000
Mersenne Twister (607 bits) 32 2607 − 14 × 108 → 4 × 1010 1000000001000000000, 2000000001000000000
WELL512a (512 bits) 32 2512 − 13 × 1015 2001002200000000

Results

To run the test on your own, please download the source code, whose comments contain compilation instructions. You must embed your generator in the code—there is no other practical way of testing in the petabyte range. You just have to modify the prngs_hwd.c file to implement the next() function of your generator.