Computing a numeric hash

We do need to define the __hash__() method properly. See section 4.4.4 of the Python Standard Library for information on computing hash values for numeric types. That section defines a hash_fraction() function, which is the recommended solution for what we're doing here. Our method looks like this:

def __hash__(self) -> int:
P = sys.hash_info.modulus
m, n = self.value, self.scale
# Remove common factors of P. (Unnecessary if m and n already coprime.)
while m % P == n % P == 0:
m, n = m // P, n // P

if n % P == 0:
hash_ = sys.hash_info.inf
else:
# Fermat's Little Theorem: pow(n, P-1, P) is 1, so
# pow(n, P-2, P) gives the inverse of n modulo P.
hash_ = (abs(m) % P) * pow(n, P - 2, P) % P
if m < 0:
hash_ = -hash_
if hash_ == -1:
hash_ = -2
return hash_

This reduces a two-part rational fraction value to a single, standardized hash. This code is copied with a few modifications from the reference manual. The core of the calculation, which is bolded in the preceding code, multiplies the numerator by the inverse of the denominator. In effect, it carries out the division of the numerator by the denominator, mod P. We can optimize this to make it more specific to our problem domain.

First, we could modify the __new__() method for this class to assure that the scale is non-zero, eliminating any need for sys.hash_info.inf. Second, we could explicitly limit the range of the scale factor to be less than sys.hash_info.modulus (generally  for 64-bit computers). We can eliminate the need to remove common factors of P. That would boil the hash down to hash_ = (abs(m) % P) * pow(n, P - 2, P) % P, sign handling, and the special case that -1 is mapped to -2.

Finally, we might want to cache the result of any hash calculation. This requires an additional slot that's only populated once, the first time a hash is requested. The pow(n, P - 2, P) expression is relatively expensive to evaluate and we don't want to compute it more often than necessary.

In the next section, we'll show how to implement a simple rounding schema for these FixedPoint objects.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset