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:

Status badges

Description (last modified by vdelecroix)

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 vdelecroix

  • Branch set to u/vdelecroix/18215
  • Commit set to 2862b49015b1c47cd0827e72764826e32bdc13e7
  • Status changed from new to needs_review

New commits:

​2862b49Trac 18215: Faster hash for quadratic number fields

comment:2 follow-up: Changed 7 years ago by jdemeyer

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 vdelecroix

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 vdelecroix

  • Cc ncohen added
  • Description modified (diff)

comment:5 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:6 Changed 7 years ago by git

  • Commit changed from 2862b49015b1c47cd0827e72764826e32bdc13e7 to 3ec20b4245a23f27931b00e54256743709e38e18

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​3ec20b4Trac 18215: Faster hash for quadratic number fields

comment:7 Changed 7 years ago by vdelecroix

Simpler implementation that is not the one of polynomials (base on 6.7.beta1).

Version 0, edited 7 years ago by vdelecroix (next)

comment:8 follow-up: Changed 7 years ago by ncohen

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 vdelecroix

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 when self.b is 0 ?

Yes. This is the same algorithm as Python hash for int/long.

comment:10 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

comment:11 Changed 7 years ago by vdelecroix

Thanks Nathann!

comment:12 Changed 7 years ago by git

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

​bee81efTrac 18215: fix a failing doctest

comment:13 Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:14 Changed 7 years ago by vbraun

  • Branch changed from u/vdelecroix/18215 to bee81efd147539fce1f0ef7f1e0351766dfe27a2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.