The hash16 function is not invertible… to make it invertible I would need to make the avalanche effect quite weak.
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 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).
Please see my code on GitHub. It is precisely what it does.
degskisays:
I’ll do that, tomorrow! It still seems like a contradiction.
degskisays:
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.
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.
Ellery Bannsays:
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!
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.
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.
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.