In software, we often need to generate random numbers. Commonly, we use pseudo-random number generators.
A simple generator is wyhash. It is a multiplication followed by an XOR:
uint64_t wyhash64_x; uint64_t wyhash64() { wyhash64_x += 0x60bee2bee120fc15; __uint128_t tmp; tmp = (__uint128_t) wyhash64_x * 0xa3b195354a39b70d; uint64_t m1 = (tmp >> 64) ^ tmp; tmp = (__uint128_t)m1 * 0x1b03738712fad5c9; uint64_t m2 = (tmp >> 64) ^ tmp; return m2; }
It generates 64-bit numbers. I was recently asked whether we could build the equivalent but a smaller scale.
What if you only wanted 16-bit integers and you wanted to follow the model of the wyhash64 function? This might be useful if you are working with a limited processor and you only had modest needs. Here is my proposal:
uint16_t wyhash16_x; uint32_t hash16(uint32_t input, uint32_t key) { uint32_t hash = input * key; return ((hash >> 16) ^ hash) & 0xFFFF; } uint16_t wyhash16() { wyhash16_x += 0xfc15; return hash16(wyhash16_x, 0x2ab); }
To use this code, you should first initialize wyhash16_x to a value of your choice. You may also be interested in replacing the increment (0xfc15) by any other odd integer. The period of this generator is 65536 meaning that after 65536 values, it comes back in full circle.
The essential idea is in the hash16 function. For a given key value, we have a map from 16-bit values to 16-bit values. The map is not invertible, in general. I pick the key value to 0xfc15. This choice “maximizes” the avalanche effect. That is, if you take a given value, hash it with hash16, then modify a single bit, and hash it again, the difference between the two outputs should have about 8 bits flipped (out of 16). That is, changing a little bit the input value should change the output a lot.
The hash16 function is not invertible… to make it invertible I would need to make the avalanche effect quite weak. With 0xfc15, its domain (set of output values) is only of size 44,114 whereas there are 65536 distinct 16-bit values. Is that bad? Well. If you generate 65536 random values between 0 and 65536, how many distinct values do you expect? The answer is about 41,427. So, if anything, my hash16 function might have too large of a domain.
If you only need to generate a few thousand 16-bit values, this simple generator might be good enough. It is also going to be fast if you have a fast 32-bit multiplier. Evidently, if you are planning to do serious number crunching, it will quickly show its limits. I did not even try to push it through standard statistical tests as none of them are designed for such small generators.
What I found interesting is that by optimizing the avalanche effect, I also got a generator that had a decent image size.
The source code I used to analyze this problem is available.
Appendix. Furthermore you can generate integer values in a range [0,s) efficiently:
uint16_t rand_range16(const uint16_t s) { uint16_t x = wyhash16(); uint32_t m = (uint32_t)x * (uint32_t)s; uint16_t l = (uint16_t)m; if (l < s) { uint16_t t = -s % s; while (l < t) { x = wyhash16(); m = (uint32_t)x * (uint32_t)s; l = (uint16_t)m; } } return m >> 16; }
Maybe, but that does not matter as the period of that PRNG [an invertible one] would be maxed at 2^16. The fact that the avalanche effect is not [or less] distributed uniformly ‘adds to the randomness’ in a way.
The period is still 2^16.
The great thing about a 16-bit PRNG (promoted by O’Neill) is that one can do exhaustive search. I’ll have a look at this statement, because I’m not sure (tomorrow, it’s getting dark here).
one can do exhaustive search
Please see my code on GitHub. It is precisely what it does.
I’ll do that, tomorrow! It still seems like a contradiction.
I see, nifty indeed.
The hash16 is invertible only for very specific key-pairs [ones one doesn’t want].
What bugs me a bit in your post [the way it’s written] is that you are calling the PRNG a hash function in a number of places. The PRNG consists of a state being updated on each call and then the state is mixed by a hash-function (similar to splitmix) and outputted. The good thing here is AFAICS that the hash function is Lehmer-style, contrary to splitmix.
It could be slightly more compact:
std::uint16_t wyhash16_x = 1u;
[[ nodiscard ]] inline std::uint16_t hash16 ( std::uint32_t hash, std::uint16_t const key ) noexcept {
hash *= key;
return ( hash >> 16 ) ^ hash;
}
[[ nodiscard ]] std::uint16_t wyhash16 ( ) noexcept {
wyhash16_x += 0xfc15;
return hash16 ( wyhash16_x, 0x2ab );
}
I’m still a bit skeptic as to your implicit assumption that good avalanche mixer implies good PRNG. Going through the same exercise for a hash32 would make that testable.
Dear Dr. Lemire,
Thank you for your nice PRNG algorithm. I am going to use it on a 6502-based computer. Doesn’t the function hash16 return a 16-bit result because of & 0xFFFF? The function definition says uint32_t. Isn’t the hash function also very expensive (on an 8-bit computer) using ((hash >> 16) ^ hash) & 0xFFFF? The ^ seems expensive. Also, do you think it would be better to change the seed (wyhash16_x) after every, let’s say, 30,000 random number generated? I have a source for a somewhat random 24-bit number generator. Please let me know what you think!
The XOR is not expensive.
The period will indeed be limited.
I stand corrected! It is XOR and I was confused with BASIC’s exponent symbol…
How does Mult-XOR compare with XOR-Shift algorithms?
Also, the generation of ranged integers, I don’t understand the line “uint16_t t = -s % s;“, doesn’t that always result in zero? Or am I confusing again, e.g. that it’s not quite t = -5 % 5 which results in 0, but actually two’s complement of 5 MOD 5.
Thanks for your prompt reply!
I have a whole blog post on this issue:
https://lemire.me/blog/2020/10/28/what-the-heck-is-the-value-of-n-n-in-programming-languages/
I was specifically looking for a 16-bit state generator, and found this! It’s awesome! 65k period is more than plenty for my small needs. But I want to confirm one thing:
If I use two different seeds, I would get two completely different number sequences correct? I want to make sure different seeds won’t produce the same sequence with different starting positions.
Thank you in advance!! Your work is inspiring!
It is my expectation but you should always check.