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:  sage6.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
 Type changed from defect to enhancement
comment:2 Changed 5 years ago by
 Branch set to u/jdemeyer/fix_hash_function_of_rationals
comment:3 Changed 5 years ago by
 Commit set to d8c1302e2720ad02ca6f6d10b08c378c08532293
comment:4 followup: ↓ 6 Changed 5 years ago by
Why is that in matrix_cyclo_dense
+ sage: hash(A) # random ^  +
How can it be random??
comment:5 Changed 5 years ago by
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
Replying to vdelecroix:
How can it be random??
Like Nathann said, it's different on 32bit and 64bit. 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
 Commit changed from d8c1302e2720ad02ca6f6d10b08c378c08532293 to c3d64c2bde1bf8a5c64c9d433e1d94004b8250ef
Branch pushed to git repo; I updated commit sha1. New commits:
c3d64c2  Doctest fixes for 32 bits

comment:8 Changed 5 years ago by
 Status changed from new to needs_review
This now passes doctests on 32bit and 64bit.
comment:9 followup: ↓ 10 Changed 5 years ago by
 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
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
 Milestone changed from sage6.9 to sage6.10
 Status changed from needs_info to needs_review
comment:12 followup: ↓ 14 Changed 5 years ago by
One failing doctest... got
sage: beta(1/2, 3*x) beta(3*x, 1/2)
on 64bit too. Why is this related to this ticket?
Vincent
comment:13 Changed 5 years ago by
 Commit changed from c3d64c2bde1bf8a5c64c9d433e1d94004b8250ef to 888430a0dd4fbfc4448d571f14ee546dab2f8ee7
Branch pushed to git repo; I updated commit sha1. New commits:
888430a  Merge tag '6.10.beta2' into t/19304/fix_hash_function_of_rationals

comment:14 in reply to: ↑ 12 Changed 5 years ago by
Replying to vdelecroix:
One failing doctest... got
sage: beta(1/2, 3*x) beta(3*x, 1/2)on 64bit 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
 Commit changed from 888430a0dd4fbfc4448d571f14ee546dab2f8ee7 to 5524971c04d75c7f85ad0e801ac865868090d5fe
Branch pushed to git repo; I updated commit sha1. New commits:
5524971  Fix random beta() doctest

comment:16 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:17 Changed 5 years ago by
Thanks!
comment:18 Changed 5 years ago by
 Branch changed from u/jdemeyer/fix_hash_function_of_rationals to 5524971c04d75c7f85ad0e801ac865868090d5fe
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Doctest fixes