2 ms·
> This is neat! How do you choose odd numbers so the final generated numbers are high quality? This was years ago, so I forget the details. But it was along th
by dragontamer 6y ago
> This is neat! How do you choose odd numbers so the final generated numbers are high quality?
This was years ago, so I forget the details. But it was along the lines of...
uint32_t hash(uint32_t seed, uint32_t k1, uint32_t k2){
return (brev(seed*k1) * k2);
}
uint32_t evaluate(uint32_t seed, uint32_t k1, uint32_t k2){
return popcnt(hash(seed, k1, k2) ^ seed);
}
The goal is to find the values of k1 and k2 that resulted in an evaluate(seed, k1, k2) close to 16-bits (aka: 50% of bits change, the definition of "avalanche condition"). There's probably some statistical test I could have done that'd be better, but GPUs have single-cycle popcount and single-cycle XOR.
I forgot exactly which search methods I used, but note that a Vega64 GPU easily reaches 10 Trillion-multiplies / second, so you can exhaustively search a 32-bit space in a ~millisecond, and a 40-bit space in just a couple of seconds.
You can therefore search the values of k1 and k2 ~8-bits at a time every few seconds. From there, plug-and-play your favorite search algorithm (genetic algorithms? Gradient descent? Random search? Simulated annealing?).
--------
After that, I'd of course run it through PractRand or BigCrush (and other tests). In all honesty: random numbers (with bottom bit set to 1) from /dev/urandom are already really good.
---------
Exhausting the 64-bit space seems unreasonable however. I was researching FNV-hashes (another multiplication-based hash), trying to understand how they chose their constants.