The Xorshift1024* random number generator fails BigCrush

In software, we use random number generators to simulate randomness. They take the form of functions which return numbers that appear random. To test their quality, we apply statistical tests. The goal standard is a statical test called BigCrush. It tests that quality of 32-bit random values.

In an earlier post, I reported that contrary to what you can read on the Xorshift Wikipedia page, the Xorshift128+ random number generator fails BigCrush. This is somewhat significant because Xorshift128+ has been widely adopted.

The Xorshift Wikipedia page also states that a more expensive generator, xorshift1024*, passes BigCrush. So I wondered, does it, indeed, pass BigCrush?

So I used my testing framework to run BigCrush. I use four different “seeds” and I only worry about a failure if it occurs with all four seeds, and with an excessively improbable p-value. Because xorshift1024* generates 64-bit outputs, and BigCrush requires 32-bit inputs, I only keep the 32 least significant bits of each word produced by xorshift1024*.

Here are my results:

 ./summarize.pl testxorshift1024star*.log
reviewing xorshift1024star lsb 32-bits
Summary for xorshift1024star lsb 32-bits (4 crushes):
- #81: LinearComp, r = 29: FAIL!! -- p-values too unlikely (1 - eps1, 1 - eps1, 1 - eps1, 1 - eps1) -- ALL CRUSHES FAIL!!

reviewing xorshift1024star lsb 32-bits (bit reverse)
Summary for xorshift1024star lsb 32-bits (bit reverse) (4 crushes):
- #80: LinearComp, r = 0: FAIL!! -- p-values too unlikely (1 - eps1, 1 - eps1, 1 - eps1, 1 - eps1) -- ALL CRUSHES FAIL!!

So xorshift1024* fails BigCrush systematically when providing the values as is (log file 1, 2, 3, 4), and it fails again with reversing the bit order (log file 1, 2, 3, 4).

So the Wikipedia entry is misleading. Both xorshift128+ and xorshift1024* fail BigCrush.

My code is available for review, and you can rerun the tests for yourself.

5 thoughts on “The Xorshift1024* random number generator fails BigCrush”

    1. Editing the Wikipedia pages requires mere seconds, I would rather that independent parties look at the evidence I provide and do the work. Maybe you’d like to volunteer to edit the couple of pages in question?

  1. It should come as no surprise that the low order bit(s) of these generators are LFSR sequences. Multiplying the output by any odd number preserves the low order bit.
    It’s not all that hard to come up with an RNG that passes TestU01.
    Replacing the ‘next’ function from the xorshift128+ generator with a variant seems to do the trick:

    uint64_t next(void) {
    uint64_t s1 = s[0];
    const uint64_t s0 = s[1];
    //const uint64_t result = s0 + s1;
    const uint64_t result = rotl64(s0, s1 & 0x3f);
    s[0] = s0;
    s1 ^= s1 <> 18) ^ (s0 >> 5); // b, c
    return result;
    }

    I have no idea whether that’s a high quality RNG, but the performance should be good on most modern processors that use a barrel shifter to implement rotate instructions. I ‘designed’ it to pass a test suite. Is an RNG that passes TestU01 necessarily ‘better’ than one that doesn’t?

    1. Is an RNG that passes TestU01 necessarily ‘better’ than one that doesn’t?

      I make no such claim myself, though if one is going to argue for statistical quality, one should have some kind of testable argument.

Leave a Reply

Your email address will not be published. Required fields are marked *