Introduction
This page reports results of our new test for Hamming-weight dependencies. 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 − 1 | 6 × 109 | 00000021 |
xoroshiro128+ | 64 | 2128 − 1 | 5 × 1012 | 00000012 |
| Tiny Mersenne Twister (64 bits) | 32 | 2127 − 1 | 8 × 1013→ | 10001021 |
| Tiny Mersenne Twister (32 bits) | 32 | 2127 − 1 | 4 × 1013→ | 10001021 |
| SFMT (607 bits) | 32 | 2607 − 1 | 4 × 108 | 001000001000 |
| dSFMT (521 bits) | 32 | 2521 − 1 | 6 × 1012 | 1001000100100010 |
| Mersenne Twister (521 bits) | 32 | 2521 − 1 | 4 × 1010 → | 1000000100000000, 2000000100000000 |
| Mersenne Twister (607 bits) | 32 | 2607 − 1 | 4 × 108 → 4 × 1010 | 1000000001000000000, 2000000001000000000 |
| WELL512a (512 bits) | 32 | 2512 − 1 | 3 × 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.