Repo with non-cryptographic bit mixer, pseudo random number generator and a hash function. The functions were found semi-algorithmically as detailed in those posts:
In short, first procedurally generated stack machines were used to find good mixer constructions. Then each construction was tuned to see how far it could be pushed and finally I decided to take the simplest most promising mixer and publish the result here.
Version 2 greatly improves the quality of the mixer by adding an initial xor-shift and adjusting the xor-shift constants. The quality of hash stream mixer is also improved. Article here.
Version 3 improves mx3::hash with better seeding and speed while maintaining the same good quality.
Here is the mixer
inline uint64_t mix(uint64_t x) {
x ^= x >> 32;
x *= 0xbea225f9eb34556d;
x ^= x >> 29;
x *= 0xbea225f9eb34556d;
x ^= x >> 32;
x *= 0xbea225f9eb34556d;
x ^= x >> 29;
return x;
}
The name 'mx3' comes from this construction (version 1), multiply then xor-shift and repeat three times (referred to as 'mxmxmx' in posts).
The prng counter based and has a 64-bit state, hence it has a cycle of 2^64. Here is the implementation
class random {
public:
explicit random(uint64_t seed) : _counter(mix(seed + C)) {}
uint64_t operator()() { return mix(_counter++); }
private:
uint64_t _counter;
};
Uses the same construction, but to favor speed a lighter version mixes the stream before finalizing the hash with 'mix'.
A short preliminary note on speed (will update if I get around to do better tests)
mixer | MSVC, Threadripper 3970span>@</span3.7GHz, ms | MSVC, i7-4790k@4GHz, ms | Clang, i7@2GHz (mac), ms | RRC |
---|---|---|---|---|
nop | 1133 | 1148 | 1300 | - |
splitmix | 4047 | 4716 | 7917 | 16 |
mx3_rev1 | 4213 | 4688 | 7557 | 21 |
mx3_rev2 | 5173 | 5975 | 10335 | >42 |
This work is to a large degree empirical without much theoretical attention. It would be interesting to know more of what properties and weaknesses mx3 has, so please don't hesitate to let me know!
The mx3 code is licensed under the CC0 license, but attribution is still appreciated!