Hi!
Just notifying you that I added your 32 lowbias32 function to libecb:
http://pod.tst.eu/http://cvs.schmorp.de/libecb/ecb.pod#BIT_MIXING_HASHING
http://cvs.schmorp.de/libecb/ecb.h
I also added the mxing function based on Sebastiona Vigna's splitmix64, which
is also given on your page.
Unfortunately, I didn't find a reverse, so I wrote one myself (and
googling the constants afterwards, I wasn't the first to do so, I wish I
had the reverse first to google the reverse function. ehm...).
So... thanks for doing and publishing your work - libecb is not a
particulalry widely-used library, but I wanted to drop you a note that
your work is actually used (also, microsoft mimalloc uses your lowbias32
function, if you didn't already now).
And last not least, other than providing an improved 64 bit function, your
page is so useful it could only be improved by also listing the reverse
for the splitmix64 function. (hint, hint, nudge, nudge, I even quote the
salient parts here so you don't even have to look elsewhere, or, heaven
forbid, do maths:
uint64_t unmix64 (uint64_t v)
{
v ^= v >> 31 ^ v >> 62; v *= 0x319642b2d24d8ec3U;
v ^= v >> 27 ^ v >> 54; v *= 0x96de1b173f119089U;
v ^= v >> 30 ^ v >> 60;
return v;
}
Finding a better 64 bit function that uses some shifts >= 32 would, of
course, be even better.
Greetings,
Marc
--
The choice of a Deliantra, the free code+content MORPG
-----==- _GNU_ http://www.deliantra.net
----==-- _ generation
---==---(_)__ __ ____ __ Marc Lehmann
--==---/ / _ \/ // /\ \/ / schmorp@schmorp.de
-=====/_/_//_/\_,_/ /_/\_\
Interesting, and thanks for the heads up, Marc! I didn't know about
mimalloc using lowbias32. In case you hadn't noticed, I've since found
some very slightly better 32-bit mixers. I haven't given them fancy names,
and the statistical difference is so small that it probably makes no
difference in practice, but they're available for use (under "more 2-round
constants"):
https://github.com/skeeto/hash-prospector#two-round-functions
Even better, the second best I've found, which itself is also better than
lowbias32, has an efficient inverse.
> Unfortunately, I didn't find a reverse, so I wrote one myself
Note lowbias32_r in the hash prospector README. I have a function in
hillclimb.c to find modular multiplicative inverses, but probably the most
convenient way these days is to use the 3-arg pow function in Python 3.8
or later:
pow(0xbf58476d1ce4e5b9, -1, 1<<64) # => 0x96de1b173f119089
Outside of the one obvious case, xorshift is a little trickier, but you
can find a code description in hillclimb.c:
https://github.com/skeeto/hash-prospector/blob/master/hillclimb.c#L410
Once you have a handle on it, you can do that one in your head. Armed with
Python for multiplicative inverse and this knowledge, you can reverse any
basic xorshift-multiply, including splittable64, on the fly. That's why I
haven't been too fussed with listing inverses.
> Finding a better 64 bit function that uses some shifts >= 32 would, of
> course, be even better.
Yup, someday I'd like to figure out how to quickly and reliably evaluate
64-bit mixers the same way I did with 32-bit so that I could find more
options.
> your page is so useful it could only be improved by also listing the
> reverse for the splitmix64 function.
Thanks, I've added the inverse to my article.