Number hash function

[fredrik-johansson]

There is a ca_hash_repr which hashes the internal representation of a ca_t. More interesting is to have a genuine hash function C -> Z to allow using hash tables to represent finite sets of numbers. Such a function must either be trivial (e.g. always return 0) or be allowed to fail (i.e. some numbers are unhashable).

Here is a possible algorithm:

1. Let z = a*x+b where a, b are some fixed complex numbers. Compute a precise enclosure of z.
2. Round the real and imaginary parts of z to 64-bit floating-point numbers with correct rounding, and return a hash of the floating-point representations.

Note:

• This will fail when the correct rounding of z cannot be deduced. This will occur with negligible probability if a, b are random.
• All sufficiently small numbers will hash to the same value, unless one sets b = 0.
• It will not work for numbers that are too large for numerical evaluation with Arb, e.g. exp(exp(exp(exp(exp(pi))))). This could be solved by fixing some huge bound H and returning 0 when |x| > H. Some some form of level-index arithmetic needs to be implemented to deal with such inequalities. Hashing will fail when the inequality cannot be evaluated.
• It will similarly not work for numbers that are too small if b = 0. As above, a lower bound 1 / H could be used.
• This will not be compatible with any conventional hash function for integers or rational numbers, e.g. hash(int) in Python. You could check if the number is an integer, but then hashing will fail for numbers where this can't be proved. Hashing in a way that is compatible with integers is perhaps better left to the user.
• Alternatively, to stay compatible with hashing for integers, you could take a = 1 and b = some number << 1, round z = a*x + b to the nearest Gaussian integer, and return a hash of the representation. You would need some cutoff for huge numbers where computing the nearest integers would be too expensive.