Opened 7 years ago
Closed 7 years ago
#18215 closed enhancement (fixed)
Huge speed up for hash of quadratic number field elements
Reported by: | vdelecroix | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.7 |
Component: | number fields | Keywords: | |
Cc: | ncohen | Merged in: | |
Authors: | Vincent Delecroix | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | bee81ef (Commits, GitHub, GitLab) | 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 7 years ago by
- Branch set to u/vdelecroix/18215
- Commit set to 2862b49015b1c47cd0827e72764826e32bdc13e7
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 7 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 7 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 7 years ago by
- Cc ncohen added
- Description modified (diff)
comment:5 Changed 7 years ago by
- Description modified (diff)
comment:6 Changed 7 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 7 years ago by
Simpler implementation that is not the one of polynomials (base on 6.7.beta1).
comment:8 follow-up: ↓ 9 Changed 7 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 7 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 7 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
comment:11 Changed 7 years ago by
Thanks Nathann!
comment:12 Changed 7 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 7 years ago by
- Status changed from needs_review to positive_review
comment:14 Changed 7 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