PRNGs.md: SplitMix32, a shift seems to be off?

[mvasilkov]

Hi,

Thanks a lot for documenting PRNGs in such a neat way!

I was wondering about the following:

SplitMix32 is a transformation of the fmix32 finalizer from MurmurHash3 into a PRNG.

You use (15, 13, 16) right-shifts in your version, but the C reference implementation uses (16, 13, 16).

The SMhasher version of MurmurHash3 also has 16 as the first right shift.

Is this difference between your version and the "upstream" fmix32 intentional?

(I also see that xxHash uses the 15 right-shift, but it has different constants, too.)

[bryc]

Hmm, thanks for bringing this up. Agreed, this is confusing.

Well I can't find a definitive source of the constants I chose before Aug 2018. Either the original source is lost or hidden, or it is entirely possible that I came up with this variant myself when posting on StackOverflow, either intentionally or accidentally.

Here's some background. I remember being interested in a SplitMix32 function after learning about SplitMix64.

I originally posted that particular function as C code on StackOverflow on Aug 28, 2018 at 10:55 as follows:

"SplitMix32", adopted from xxHash/MurmurHash3 (Weyl sequence):

uint32_t splitmix32(void) {
    uint32_t z = state += 0x3504f333;
    z ^= z >> 15; // 16 for murmur3
    z *= 0x85ebca6b;
    z ^= z >> 13;
    z *= 0xc2b2ae3d; // 0xc2b2ae35 for murmur3
    return z ^= z >> 16;
}

• 0x3504f333 appears to be a constant from a Weyl Sequence function that I was probably looking at. Original source might be http://marc-b-reynolds.github.io/math/2016/03/29/weyl_hash.html.
• 0xc2b2ae3d is from xxhash, whereas 0xc2b2ae35 is murmur3 - I listed both. Same for 15 (for xxhash) and 16 (murmur3).

Interestingly, in this initial version, the first constant is the one from MurmurHash3, but the second one was initially xxHash. After just one day I edited the post, changing the second constant to match MurmurHash3. But I left the 15. It also seems that this might be the source people are taking this function from.

The changed function for reference:

uint32_t splitmix32(void) {
    uint32_t z = state += 0x9e3779b9;
    z ^= z >> 15; // 16 for murmur3
    z *= 0x85ebca6b;
    z ^= z >> 13;
    z *= 0xc2b2ae35;
    return z ^= z >> 16;
}

---

Someone independently took note of this variant and seemed to have found it's slightly better than the original:

A seemingly popular variation of SplitMix32 changes the first bitshift length from 16 to 15. It is included under the name splitmix32a in this repository, and fares slightly better than plain splitmix32 in Crush and BigCrush tests (5 or 4 failures in Crush, 9 in BigCrush). In PractRand, this variation fails during the 1 GB stage, whereas plain splitmix32 fails in the preceding 512 MB round.

I suppose if it is technically better as a PRNG, that's a silver lining. Though I truly cannot remember if I had a good reason to change the constants.

He also mentions an additional splitmix32b variant with even more slightly better statistics.

Anyway, as far as resolving this issue - I could restore the shift value to 16, or I could simply add a note that says "the shift value of 15 apparently performs slightly better in testing, but I have no clue why". Let me know if you have any further thoughts.

[bryc]

Closing issue. I just added a note to clarify that the constants tend to change between implementations, and that certain constants perform better than the original MurmurHash3 constants.