Opened 6 years ago
Closed 6 years ago
#18215 closed enhancement (fixed)
Huge speed up for hash of quadratic number field elements
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  number fields  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  bee81ef (Commits)  Commit:  bee81efd147539fce1f0ef7f1e0351766dfe27a2 
Dependencies:  Stopgaps: 
Description (last modified by )
Before
sage: L.<a> = QuadraticField(7) sage: b = a  13/7 sage: timeit("hash(b)") 625 loops, best of 3: 54 µs per loop
After
sage: L.<a> = QuadraticField(7) sage: b = a  13/7 sage: timeit("hash(b)") 625 loops, best of 3: 97.7 ns per loop
... looks like a x500 speed up :)
As a consequence (and with #18213 applied) Before
sage: %time gr = polytopes.great_rhombicuboctahedron() CPU times: user 5.68 s, sys: 68 ms, total: 5.75 s Wall time: 5.7 s
After
sage: %time gr = polytopes.great_rhombicuboctahedron() CPU times: user 2.71 s, sys: 36 ms, total: 2.75 s Wall time: 2.69 s
See also: #18226
Change History (14)
comment:1 Changed 6 years ago by
 Branch set to u/vdelecroix/18215
 Commit set to 2862b49015b1c47cd0827e72764826e32bdc13e7
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 6 years ago by
Is there a reason why the hash should be the same as the one for the polynomial?
comment:3 in reply to: ↑ 2 Changed 6 years ago by
Replying to jdemeyer:
Is there a reason why the hash should be the same as the one for the polynomial?
No idea. But it make sense. It was the previous implementation. I did not want to break anything.
On the other hand, it does not take the parent into account and 'sqrt(2) + 3/2' and 'sqrt(3) + 3/2' would have the same hash.
What do you think?
comment:4 Changed 6 years ago by
 Cc ncohen added
 Description modified (diff)
comment:5 Changed 6 years ago by
 Description modified (diff)
comment:6 Changed 6 years ago by
 Commit changed from 2862b49015b1c47cd0827e72764826e32bdc13e7 to 3ec20b4245a23f27931b00e54256743709e38e18
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3ec20b4  Trac 18215: Faster hash for quadratic number fields

comment:7 Changed 6 years ago by
Simpler implementation that is not the one of polynomials (based on 6.7.beta1).
comment:8 followup: ↓ 9 Changed 6 years ago by
Hello,
Can you tell where this 42082631
comes from? Also, is it true that mpz_pythonhash(self.b)
is zero when self.b
is 0 ? It must hold if you want the hash of this element and the hash defined on Q to match.
comment:9 in reply to: ↑ 8 Changed 6 years ago by
Replying to ncohen:
Hello,
Can you tell where this
42082631
comes from?
This is to avoid conflicts for small values of a
and b
. It avoids conflicts between a=1, b=1
and a=b=0
.
Also, is it true that
mpz_pythonhash(self.b)
is zero whenself.b
is 0 ?
Yes. This is the same algorithm as Python hash for int/long
.
comment:10 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
comment:11 Changed 6 years ago by
Thanks Nathann!
comment:12 Changed 6 years ago by
 Commit changed from 3ec20b4245a23f27931b00e54256743709e38e18 to bee81efd147539fce1f0ef7f1e0351766dfe27a2
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
bee81ef  Trac 18215: fix a failing doctest

comment:13 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:14 Changed 6 years ago by
 Branch changed from u/vdelecroix/18215 to bee81efd147539fce1f0ef7f1e0351766dfe27a2
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac 18215: Faster hash for quadratic number fields