Applying the RRC-64-test to the degski64 and Lea64 mixers

In LXM: better splittable pseudorandom number generators (and almost as fast) by Guy L Steele and Sebastiano Vigna, approaches for pseudo-random number generation through mixing PRNGs with different structure by way of a non-linear mixer are discussed. The three 64-bit mixers considered in the paper are Austin Appleby's Murmur3 (and Stafford's Variant 13 of Murmur3), of which I've written about here and here, degski64 and Lea64, described in the LXM paper.

degski64 and Lea64 are similar to Murmur3 in structure but use xor-shifts by 32 bits exclusively (Murmur3 included for reference):

uint64_t murmur64(uint64_t z) {
  z ^= (z >> 33);
  z *= 0xff51afd7ed558ccdull;
  z ^= (z >> 33);
  z *= 0xc4ceb9fe1a85ec53ull;
  return z ^ (z >> 33);
}

uint64_t lea64(uint64_t z) {
  z ^= (z >> 32);
  z *= 0xdaba0b6eb09322e3ull;
  z ^= (z >> 32);
  z *= 0xdaba0b6eb09322e3ull;
  return z ^ (z >> 32);
}

uint64_t degski64(uint64_t z) {
  z ^= (z >> 32);
  z *= 0xd6e8feb86659fd93ull;
  z ^= (z >> 32);
  z *= 0xd6e8feb86659fd93ull;
  return z ^ (z >> 32);
}

I am not aware of the design rationale for the 32 bit shifts; one would think that they would be faster on some platforms. A short test with clang-12 on a Ryzen 5900X gives timings for the 4 functions that are within 0.5% of each other, my guess is that they are equally fast (sampled 200 Gops/each mixer, ~2.57 Gops/s).

Applying RRC-64 to degski64 and Lea64

Sadly, neither mixer is particularly strong but fails RRC-64 about as badly as the original Murmur3/Variant13. Moremur is, at least as far as RRC-64 goes, a much stronger mixer with the same number of operations.

As can be seen from the tables below, the constants used in degski64 and Lea64 are no stronger (w.r.t. RRC-64) than Murmur3/Variant 13 but much weaker than Moremur.

degski64 failures, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	17	15	17	15	15	16	15	15	17	16	15	15	14	15	15		14	14	14	15	14	17	16	15	17	16	17	15	15	17	16	15
16	14	15	15	15	15	15	15	15	15	15	15	15	15	15	15	16		17	15	16	15	16	16	15	17	15	15	15	15	17	15	17	16
32	16	16	15	17	15	15	16	15	15	17	16	16	14	14	14	15		14	14	14	15	14	17	16	15	17	16	15	15	15	17	16	15
48	14	15	15	15	15	15	15	15	15	15	15	15	15	15	15	17		17	15	16	15	17	16	15	17	15	15	15	15	17	16	17	17
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	17	15	17	15	15	16	16	15	16	16	15	14	14	14	15		14	14	16	15	14	17	15	15	17	16	15	15	15	17	16	15
16	14	15	15	15	15	15	14	15	15	15	15	15	15	15	16	16		17	15	16	15	17	16	15	17	15	15	15	15	17	15	17	16
32	15	16	15	17	15	15	16	15	15	16	15	16	14	14	15	15		14	14	14	15	14	17	15	15	17	16	15	15	15	17	16	15
48	14	15	15	15	15	15	15	15	14	15	15	15	15	15	16	17		17	15	16	15	17	16	15	17	15	15	15	15	17	15	17	17

Lea64 failures, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	17	15	17	15	15	16	15	15	17	16	15	15	14	15	15		14	14	14	15	14	17	16	15	17	16	17	15	15	17	16	15
16	14	15	15	15	15	15	15	15	15	15	15	15	15	15	15	16		17	15	16	15	16	16	15	17	15	15	15	15	17	15	17	16
32	16	16	15	17	15	15	16	15	15	17	16	16	14	14	14	15		14	14	14	15	14	17	16	15	17	16	15	15	15	17	16	15
48	14	15	15	15	15	15	15	15	15	15	15	15	15	15	15	17		17	15	16	15	17	16	15	17	15	15	15	15	17	16	17	17
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	17	15	17	15	15	16	16	15	16	16	15	14	14	14	15		14	14	16	15	14	17	15	15	17	16	15	15	15	17	16	15
16	14	15	15	15	15	15	14	15	15	15	15	15	15	15	16	16		17	15	16	15	17	16	15	17	15	15	15	15	17	15	17	16
32	15	16	15	17	15	15	16	15	15	16	15	16	14	14	15	15		14	14	14	15	14	17	15	15	17	16	15	15	15	17	16	15
48	14	15	15	15	15	15	15	15	14	15	15	15	15	15	16	17		17	15	16	15	17	16	15	17	15	15	15	15	17	15	17	17

Moremur failures, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	19	19	19	22	22	24	25	28	27	28	29	16	16	16	17		16	17	19	19	20	28	27	28	34	29	29	35	36	37	37	38
16	17	17	18	19	19	19	19	20	21	22	23	23	24	25	26	27		36	35	35	39	40	34	31	31	39	40	39	38	37	34	34	36
32	28	29	30	31	31	32	33	33	34	34	34	34	34	33	32	32		28	34	33	32	32	31	33	33	34	34	34	35	35	36	37	36
48	32	28	28	28	29	29	29	29	30	30	30	30	31	31	31	32		31	31	31	33	36	37	36	28	33	34	31	31	28	25	22	19
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	19	19	19	22	22	24	25	28	29	18	28	15	16	16	17		16	17	19	21	21	26	28	30	34	31	34	34	36	36	37	37
16	17	18	18	19	19	19	19	19	21	22	23	24	24	25	26	27		36	35	35	39	40	34	31	31	39	40	39	38	37	34	34	36
32	28	29	30	30	32	33	33	34	34	35	35	34	34	32	33	32		28	34	33	32	32	31	33	33	34	34	34	35	36	36	36	36
48	32	28	28	28	28	28	29	29	29	30	30	30	31	31	32	32		31	31	31	33	35	35	34	28	32	32	31	30	28	25	22	19

Conclusion

It would be interesting to see to what extent a (much) stronger mixer would affect the results in the LXM paper. I believe that Moremur is a stronger drop-in replacement for Murmur3, Variant13, degski64 and Lea64 with comparable, if not identical, speed.