mardi 22 décembre 2015

What is the real definition of the xorshift128+ algorithm?

I have need of a good pseudo random number generator (PRNG), and it seems like the current state of the art is the xorshift128+ algoritm. Unfortunately, I have discovered 2 different versions. The one on wikipedia: Xorshift shows as:

uint64_t s[2];

uint64_t xorshift128plus(void) {
    uint64_t x = s[0];
    uint64_t const y = s[1];
    s[0] = y;
    x ^= x << 23; // a
    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
    return s[1] + y;
}

Which seems straight forward enough. What's more, the edit logs appear to show that this code snippet was added by a user named "Vigna", which is presumably "Sebastiano Vigna" who is the author of the paper on xorshift128+: Further scramblings of Marsaglia’s xorshift generators. Unfortunately, the implementation in that paper is slightly different:

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

Apart from some different names, these two snippets are identical except for the final two shifts. In the Wikipedia version those shifts are by 17 and 26, while the shifts in the paper are by 18 and 5.

Does anyone know which is the "right" algorithm? Does it make a difference? This is apparently a fairly widely used algorithm - but which version is used?




Aucun commentaire:

Enregistrer un commentaire