hash of mpz_t and mpq_t

Hans Åberg haberg-1 at telia.com
Wed Jun 16 20:29:13 UTC 2021

> On 16 Jun 2021, at 21:58, Marc Glisse <marc.glisse at inria.fr> wrote:
> On Tue, 15 Jun 2021, Hans Åberg wrote:
>> GMP C++ has several issues: requires a special compile,

One needs a special configure option I think, so if a system comes with a default, it will not work.

> ?
> Are you referring to the lack of support for visual studio?
>> very complicated templates,
> doesn't seem very relevant to a user, while performance is.

I did not see any point in it, in view of C++11 move operators and C++17 copy elision. Maybe in earlier C++ versions it limited optimization would make sense to some.

However, I wrote my version before there was anything in GMP, and it fulfills my needs. :-)

>> and move operators implemented using swap.
> What's wrong with a move assignment using swap? (move construction does not use swap)
> Maybe you would prefer if it released the memory of the moved-from object immediately? That's a trade-off, releasing memory early is nice, but keeping the memory may save the need for an allocation.

Slow and destruction sequence gets out of order, which can cause problems. There are articles on the net about it. A fad in early C++11 programming because the standard permits it.

>> The C++ standard comes with hash functions
> The C++ standard still doesn't provide a function to hash a pair of int. They are currently discussing again what a good hashing facility should look like, including how to use a seed, and without restricting the size of the state/seed to size_t.

Then people typically use what I indicated, an exclusive or ^ maybe with a left shift <<.

>> for use with its containers std::unordered_map etc, which is was asked for. Typically, one wants something fast here.
> There we agree that std::hash is meant for use in hash maps, and should not be used for cryptographic purposes.

Right, and conversely, say SHA would be overkill in a hash map container.

> I think I'd be in favor of a mpz_hash(mpz_t, seed) as described by Mathieu (I have requested similar things in the past https://gmplib.org/list-archives/gmp-discuss/2015-November/005880.html), with suitable documentation, but I am leaving that to more knowledgeable maintainers.

I added the size to the hash. Best to test out with some profiling, though not in my scope.

namespace std {
  template<> struct hash<gmp::integer> {
    size_t operator()(gmp::integer const& x) const {
      std::size_t h = 0;
      for (mp_size_t i = 0; i < mpz_size(x.value_); ++i)
        h ^= std::hash<mp_limb_t>()(mpz_getlimbn(x.value_, i));
      return h ^ std::hash<mp_size_t>()(x.value_->_mp_size);
} // namespace std

More information about the gmp-discuss mailing list