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:

Status badges

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 embray

  • Milestone changed from sage-8.6 to sage-8.7

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.

comment:2 Changed 3 years ago by embray

  • 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 embray

  • 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: Changed 9 months ago by vdelecroix

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 mmezzarobba

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: Changed 9 months ago by 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

Is there some way to check quickly if an element is rational?

comment:7 in reply to: ↑ 6 ; follow-up: Changed 9 months ago by 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))                                                                                       
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 tscrim

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))                                                                                       
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?

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?

Note: See TracTickets for help on using tickets.