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 for some parameter choice the 607-bit Mersenne Twister 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. Indeed, the wide variation in quality suggests that the dynamic generation of parameters performed therein is not reliable.

PRNG w Period p = 10−20 @ Faulty signature
xorshift128+ 64 2128 − 16 × 109 00000021
xoroshiro128+64 2128 − 18 × 1012 00000012
Tiny Mersenne Twister (127 bits) 32 2127 − 16 × 1014 10001021
Mersenne Twister (521 bits) 32 2521 − 14 × 10101000000100000000, 2000000100000000
Mersenne Twister (607 bits) 32 2607 − 14 × 108 — 4 × 1010 1000000001000000000, 2000000001000000000

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.