Hash functions

Piotr Wyderski wyderski at ii.uni.wroc.pl
Mon May 3 15:36:05 CEST 2004


I am developing a project which uses a huge amount of
multiprecision objects. Their values come, however,
from a relatively small domain, so I decided to introduce
a layer of indirection and to use pointers to the objects
instead of the objects themselves. The objects are kept
in a hashtable (there always exist only one instance of
an object with a given value). And here comes the problem:
as far as I know there is no support for hashing in the
GMP package. There is a need for a consistent family of
functions called, say, unsigned int mpX_hash(mpX_t p),
where X is one of {z,f,q}. This feature should be added
to the library because it is very useful and very hard
to implement outside it, since it must have full access
to the guts of the object. It's not a big problem if
it is for mpz_t, since there's the function mpz_getlimbn(),
but this way doesn't work for the other types because
they are implemented differently. Currently I use this:

        static inline unsigned int hash(const mpf_class& p) {

            unsigned int h = 2166136261U;

            // Fowler, Noll and Vo hashing

            for(int i = 0U; i < p.get_mpf_t()->_mp_size; ++i) {

                h *= 16777619U;
                h ^= p.get_mpf_t()->_mp_d[i];

            return h;

which is extremely unportable and illegal. Could you
please extend the library (including its C++ interface)?

    Best regards
    Piotr Wyderski

More information about the gmp-discuss mailing list