hash of mpz_t and mpq_t

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

> On 15 Jun 2021, at 23:24, Marco Bodrato <bodrato at mail.dm.unipi.it> wrote:
> Il 2021-06-15 19:03 Hans Åberg ha scritto:
>>> ...
> If one wants a hash giving the same result everywhere, then I agree with the way proposed by Torbjörn: using mpz_export and an hash function on the result.
> The drawback is that it requires to allocate a new buffer.

That should be avoided as memory allocations can be very time expensive.

> I'd additionally suggest to handle the sign in some way if one does not like to obtain the same hash for 1 and -1, 2 and -2, ... n and -n.

The hash container will only be somewhat thicker without it.

Otherwise using _mp_d ^ (mp_limb_t)_mp_size might do.

>> The C++ standard comes with hash functions for use with its containers
>> std::unordered_map etc, which is was asked for. Typically, one wants
>> something fast here.
> But maybe "something fast" is not always good enough for all contexts.
> If a hash must is needed for "random" numbers, I'd suggest mpz_get_ui(Z), it ishash  fast.

Numbers need only to be random enough to flatten the container on large sets of keys stored.

What I suggested is what is typically used with the C++ containers: In addition to the exclusive or ^, some may put in a shift <<.

> If one doesn't care to obtain different results on different machines, then building a hash from the array pointed by mpz_limbs_read(Z) seems a good idea (it does not need an additional buffer); possibly taking into account not only the mpz_size(Z), but also the mpz_sign(Z).

For C++, it depends on the compiler even: you can't rely on gcc and clang doing the same.

More information about the gmp-discuss mailing list