Opened 3 years ago
Last modified 9 months ago
#26944 new enhancement
Improve hashing of algebraic numbers
Reported by: | mmezzarobba | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | number fields | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As suggested by Pascal Molin, the hash of an element α of QQbar/AA could be based on that element perturbed by a transcendental number, to avoid triggering exact computations even in unlucky cases.
(There is a comment in AlgebraicNumber_base.__hash__()
noting that the effort to avoid exact computation is probably wasted because we'll do a comparison if the hashes match, but this ignores the common case where we are retrieving an element of a hash table using the same physical object that was stored as a key.)
See also #26898.
Change History (8)
comment:1 Changed 3 years ago by
- Milestone changed from sage-8.6 to sage-8.7
comment:2 Changed 3 years ago by
- Milestone changed from sage-8.7 to sage-8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:3 Changed 3 years ago by
- Milestone sage-8.8 deleted
As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).
comment:4 follow-up: ↓ 6 Changed 9 months ago by
This is a nice idea except that we want that the hash to be consistent with rational numbers. More precisely we want to preserve hash(2/3) == hash(AA(2/3))
. I don't see how the perturbation approach would work under this constraint.
comment:5 Changed 9 months ago by
I agree. If we do want to preserve that property, the problem is unsolvable. (Yet another argument for not trying to drop this requirement, IMO...)
comment:6 in reply to: ↑ 4 ; follow-up: ↓ 7 Changed 9 months ago by
Replying to vdelecroix:
More precisely we want to preserve
hash(2/3) == hash(AA(2/3))
.
Note that this is not the case currently:
sage: hash(2/3) -3523014627193176564 sage: hash(QQbar(2/3)) -8445525302856973090 sage: hash(AA(2/3)) 3067781198362510072
Is there some way to check quickly if an element is rational?
comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 9 months ago by
Replying to tscrim:
Replying to vdelecroix:
More precisely we want to preserve
hash(2/3) == hash(AA(2/3))
.Note that this is not the case currently:
sage: hash(2/3) -3523014627193176564 sage: hash(QQbar(2/3)) -8445525302856973090 sage: hash(AA(2/3)) 3067781198362510072
Thanks Travis. Indeed, the hash is not compatible with anything because of AA_hash_offset
and QQbar_hash_offset
. However is it desirable to have them compatible with rationals? Or at least integers?
Is there some way to check quickly if an element is rational?
No. You need to compute the degree of the minimal polynomial (ie exactify). However there are numerical tricks to guess (and works well if the denominator is not too big).
comment:8 in reply to: ↑ 7 Changed 9 months ago by
Replying to vdelecroix:
Replying to tscrim:
Replying to vdelecroix:
More precisely we want to preserve
hash(2/3) == hash(AA(2/3))
.Note that this is not the case currently:
sage: hash(2/3) -3523014627193176564 sage: hash(QQbar(2/3)) -8445525302856973090 sage: hash(AA(2/3)) 3067781198362510072Thanks Travis. Indeed, the hash is not compatible with anything because of
AA_hash_offset
andQQbar_hash_offset
. However is it desirable to have them compatible with rationals? Or at least integers?
Probably because of the fact coercion makes them be ==
.
Is there some way to check quickly if an element is rational?
No. You need to compute the degree of the minimal polynomial (ie exactify). However there are numerical tricks to guess (and works well if the denominator is not too big).
Perhaps we could use some test that discards a number of cases when the element is definitely not rational? Then for the cases that remain, we run exactify
? Would there be other issues with equality and hashing that could come up without calling exactify
?
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.