Message326929
> SeaHash seems to be designed for 64 bits.
Absolutely.
> I'm guessing that replacing the shifts by
>
> x ^= ((x >> 16) >> (x >> 29))
>
> would be what you'd do for a 32-bit hash.
My guess too. But "the prime" is a puzzle. As noted before, the 64-bit prime is specially constructed to satisfy specific dispersion properties. While I haven't triple-checked this, I believe it fails at two specific bit positions:
- Bit 2**16 doesn't propagate into the leading 4 bits at all.
- Bit 2**17 does propagate into bit 2**60, but _only_ into that bit among the highest 4 bits. One of the criteria is that the prime shouldn't propagate a lower-order bit into _only_ the least-significant of the 4 leading bits.
Repairing that would probably require adding a bit or two. But the prime already has 35 bits set. The greater the imbalance between 0 and 1 bits, the more multiply acts like a simpler sequence of shift-and-adds or shift-and-subtracts (for example, at an extreme, consider the multiplier (1 << 63) - 1).
Anyway, it seems the density of 1 bits would have to be even higher for a 32-bit multiplier to ensure all low-order bits directly propagated to at least one of the topmost 3 bits, but not to the third-most significant alone.
Or I could search for a 31-bit prime - or just an odd integer - that got as close as possible with 16 or 17 bits set. Or ...
> Alternatively, we could always compute the hash with
> 64 bits (using uint64_t) and then truncate at the end
> if needed.
Provided we continue to like it at all ;-) In which case I'd probably end it with
32_bit_result = (32_bit_result_type)(x ^ (x >> 32));
instead. |
|
Date |
User |
Action |
Args |
2018-10-03 01:15:06 | tim.peters | set | recipients:
+ tim.peters, rhettinger, mark.dickinson, eric.smith, jdemeyer, sir-sigurd |
2018-10-03 01:15:05 | tim.peters | set | messageid: <1538529305.32.0.545547206417.issue34751@psf.upfronthosting.co.za> |
2018-10-03 01:15:05 | tim.peters | link | issue34751 messages |
2018-10-03 01:15:04 | tim.peters | create | |
|