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 searchPlease 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

hash16return 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 inzero? Or am I confusing again, e.g. that it’s not quitet = -5 % 5which results in 0, but actuallytwo’s complement of 5MOD 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.