Opened 5 years ago

Closed 5 years ago

#19304 closed enhancement (fixed)

Fix hash function of rationals

Reported by: vdelecroix Owned by:
Priority: critical Milestone: sage-6.10
Component: misc Keywords:
Cc: ncohen Merged in:
Authors: Jeroen Demeyer Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 5524971 (Commits) Commit: 5524971c04d75c7f85ad0e801ac865868090d5fe
Dependencies: Stopgaps:

Description

sage: 1 == hash(2/3) == hash(3/2) == hash(5/4) == hash(4/5) == hash(9/8) == hash(8/9)
True

The hash function of rationals is only a xor between numerator and denominator. As shown above this is too naive to avoid collisions!

Change History (18)

comment:1 Changed 5 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Type changed from defect to enhancement

comment:2 Changed 5 years ago by jdemeyer

  • Branch set to u/jdemeyer/fix_hash_function_of_rationals

comment:3 Changed 5 years ago by git

  • Commit set to d8c1302e2720ad02ca6f6d10b08c378c08532293

Branch pushed to git repo; I updated commit sha1. New commits:

d8c1302Doctest fixes

comment:4 follow-up: Changed 5 years ago by vdelecroix

Why is that in matrix_cyclo_dense

+            sage: hash(A)  # random
                                 ^
                                 |
 --------------------------------+

How can it be random??

comment:5 Changed 5 years ago by ncohen

probably a trick for 32bits/64bits.

"# random" reads "random", but it has the same effect as "# ignore_output_but_check_that_no_exception_is_raised".

Nathann

comment:6 in reply to: ↑ 4 Changed 5 years ago by jdemeyer

Replying to vdelecroix:

How can it be random??

Like Nathann said, it's different on 32-bit and 64-bit. Since the doctest is really about (im)mutability, the actual hash value doesn't matter, so I used # random.

comment:7 Changed 5 years ago by git

  • Commit changed from d8c1302e2720ad02ca6f6d10b08c378c08532293 to c3d64c2bde1bf8a5c64c9d433e1d94004b8250ef

Branch pushed to git repo; I updated commit sha1. New commits:

c3d64c2Doctest fixes for 32 bits

comment:8 Changed 5 years ago by jdemeyer

  • Status changed from new to needs_review

This now passes doctests on 32-bit and 64-bit.

comment:9 follow-up: Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_info

There are fractions in Python3, shouldn't we try to be complient with it?

>>> import fractions
>>> fractions.Fraction(2,3)
Fraction(2, 3)
>>>  hash(fractions.Fraction(2,3))
768614336404564651

The code is actually pure python and takes care of exactly representable float... and Python seems to have a different politics than Sage to that respect.

    def __hash__(self):
        """hash(self)

        Tricky because values that are exactly representable as a
        float must have the same hash as that float.

        """
        # XXX since this method is expensive, consider caching the result
        if self._denominator == 1:
            # Get integers right.
            return hash(self._numerator)
        # Expensive check, but definitely correct.
        if self == float(self):
            return hash(float(self))
        else:
            # Use tuple's hash to avoid a high collision rate on
            # simple fractions.
            return hash((self._numerator, self._denominator))

comment:10 in reply to: ↑ 9 Changed 5 years ago by jdemeyer

Replying to vdelecroix:

There are fractions in Python3, shouldn't we try to be complient with it?

Also Python 2 by the way. Not sure if it's important that Sage is compatible with that. It's easy to do that, but also more expensive.

comment:11 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-6.9 to sage-6.10
  • Status changed from needs_info to needs_review

comment:12 follow-up: Changed 5 years ago by vdelecroix

One failing doctest... got

sage: beta(1/2, 3*x)
beta(3*x, 1/2)

on 64-bit too. Why is this related to this ticket?

Vincent

comment:13 Changed 5 years ago by git

  • Commit changed from c3d64c2bde1bf8a5c64c9d433e1d94004b8250ef to 888430a0dd4fbfc4448d571f14ee546dab2f8ee7

Branch pushed to git repo; I updated commit sha1. New commits:

888430aMerge tag '6.10.beta2' into t/19304/fix_hash_function_of_rationals

comment:14 in reply to: ↑ 12 Changed 5 years ago by jdemeyer

Replying to vdelecroix:

One failing doctest... got

sage: beta(1/2, 3*x)
beta(3*x, 1/2)

on 64-bit too. Why is this related to this ticket?

Ginac reorders the arguments to beta() according to their hash. Symbolic expressions (like 3*x) have a "random" hash: it is different in different runs of Sage. I'll change the doctest to something which does not involve random hashes.

comment:15 Changed 5 years ago by git

  • Commit changed from 888430a0dd4fbfc4448d571f14ee546dab2f8ee7 to 5524971c04d75c7f85ad0e801ac865868090d5fe

Branch pushed to git repo; I updated commit sha1. New commits:

5524971Fix random beta() doctest

comment:16 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:17 Changed 5 years ago by jdemeyer

Thanks!

comment:18 Changed 5 years ago by vbraun

  • Branch changed from u/jdemeyer/fix_hash_function_of_rationals to 5524971c04d75c7f85ad0e801ac865868090d5fe
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.