Opened 4 years ago
Closed 4 years ago
#23402 closed enhancement (fixed)
faster hash of number field elements
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  number fields  Keywords:  days88, IMA coding sprints 
Cc:  bhutz  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  8d8a2ea (Commits, GitHub, GitLab)  Commit:  8d8a2ea708b6fbb8aaa22f5fec07d6bbc4a96d9a 
Dependencies:  #23388  Stopgaps: 
Description (last modified by )
Hashing of nf element go through self.polynomial()
which is damn slow!
The attached branch provides a quick hash version (that is more robust than the one for polynomial). A x10 speed up is seen on the following example (425 ms vs 40ms)
sage: K.<b> = NumberField(x^3  2) sage: l = [i * b + j * b^2 for i in range(100) for j in range(100)] sage: l.sort() sage: %time s = set(l[i+1]  l[i] for i in range(len(l)1))
Change History (29)
comment:1 Changed 4 years ago by
 Branch set to u/vdelecroix/23402
 Commit set to 2873d21f869dabd15a7df049dfa2262706b74893
 Dependencies set to #23388
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Description modified (diff)
comment:3 Changed 4 years ago by
Where did the two magic numbers come from? Also, why is one is hex and the other in decimal?
comment:4 Changed 4 years ago by
These "magic numbers" are just used to randomize the bits and can be obtained via
sage: phi = (1 + sqrt(5))/2 sage: hex(int(2^32 / phi)) '0x9e3779b9' sage: int(phi * 2^62) 7461864723258187525
The 7461864723258187525
was not chosen by me but comes from the hash value of rationals...
I can actually be more coherent and use the same value in both places.
comment:5 Changed 4 years ago by
... bad idea (got stupid collisions)
comment:6 Changed 4 years ago by
 Commit changed from 2873d21f869dabd15a7df049dfa2262706b74893 to 862184f6f277732287d2ffdf8aa06db8a94a7269
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
862184f  23402: faster hash for nf elements

comment:7 Changed 4 years ago by
More coherent version in 8124ba5
where both values are:
 63 bits
 documented
 in decimal notation
comment:8 Changed 4 years ago by
 Commit changed from 862184f6f277732287d2ffdf8aa06db8a94a7269 to 8124ba562387db04596077ba178d1fca154d0ab3
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8124ba5  23402: faster hash for nf elements

comment:9 Changed 4 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Okay, thanks. LGTM.
comment:10 Changed 4 years ago by
 Status changed from positive_review to needs_work
Changing the hash is changing the order of display in sets... some doctests break.
comment:11 Changed 4 years ago by
 Commit changed from 8124ba562387db04596077ba178d1fca154d0ab3 to 47780570267859ae89fc66341eea97e9ead7fd2d
Branch pushed to git repo; I updated commit sha1. New commits:
4778057  23402: fix doctests23402: fix doctests

comment:12 Changed 4 years ago by
 Commit changed from 47780570267859ae89fc66341eea97e9ead7fd2d to 9de6f1881aaa2160081585490d70b698bfd5cbdf
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
9de6f18  23402: fix doctests

comment:13 Changed 4 years ago by
 Description modified (diff)
comment:15 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:16 Changed 4 years ago by
Fails on 32bit:
sage t long src/sage/rings/number_field/number_field_element.pyx ********************************************************************** File "src/sage/rings/number_field/number_field_element.pyx", line 2888, in sage.rings.number_field.number_field_element.NumberFieldElement.__hash__ Failed example: len(set(map(hash, elts))) == len(elts) Expected: True Got: False ********************************************************************** 1 item had failures: 1 of 9 in sage.rings.number_field.number_field_element.NumberFieldElement.__hash__ [1084 tests, 1 failure, 827.34 s]
comment:17 Changed 4 years ago by
Indeed... 3 collisions in 32 bits! Probabilistically, we should not see any collision before a sample of size 2^{16} = sqrt(2^{32}).
comment:18 Changed 4 years ago by
 Commit changed from 9de6f1881aaa2160081585490d70b698bfd5cbdf to ab28ce8a7d7dd60a1b426b16462f53645cee5f4f
 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:
ab28ce8  23402: better magic numbers avoiding small collisions

comment:19 Changed 4 years ago by
needs review (no collision on the 18 first bits which is more than enough for 32 bits)
comment:20 Changed 4 years ago by
 Status changed from needs_review to needs_work
Doctest order failures due to the new hash. See patchbot report.
comment:21 Changed 4 years ago by
 Commit changed from ab28ce8a7d7dd60a1b426b16462f53645cee5f4f to 9d0329f8d1440e53a3195cd24e9fdeb518ec9775
comment:22 Changed 4 years ago by
 Status changed from needs_work to needs_review
(rebased with a new commit to fix the doctests)
comment:23 Changed 4 years ago by
 Commit changed from 9d0329f8d1440e53a3195cd24e9fdeb518ec9775 to 8d8a2ea708b6fbb8aaa22f5fec07d6bbc4a96d9a
Branch pushed to git repo; I updated commit sha1. New commits:
8d8a2ea  23402: one more doctest fix

comment:24 Changed 4 years ago by
The second doctest change in 8d8a2ea708
looks fishy. Actually, the version after my changes looks better!!
comment:25 Changed 4 years ago by
 Cc bhutz added
@bhutz: Ben can you have a look at the doctest change in invariants_of_degree
? The first change just a reordering. But the second one reproduced below looks like there was something very wrong before
sage: S3 = MatrixGroup(SymmetricGroup(3)) sage: chi = S3.character(S3.character_table()[0]) sage: S3.invariants_of_degree(5, chi=chi)  [x*y + (2*izeta3^3 + 3*izeta3^2 + 8*izeta3 + 3)*x*z + (2*izeta3^3   3*izeta3^2  8*izeta3  4)*y*z,  x^2 + (2*izeta3^3  3*izeta3^2  8*izeta3  4)*y^2 + (2*izeta3^3 +  3*izeta3^2 + 8*izeta3 + 3)*z^2] + [x0^4*x1  x0*x1^4  x0^4*x2 + x1^4*x2 + x0*x2^4  x1*x2^4, + x0^3*x1^2  x0^2*x1^3  x0^3*x2^2 + x1^3*x2^2 + x0^2*x2^3  x1^2*x2^3]
comment:26 followup: ↓ 27 Changed 4 years ago by
Actually, it looks like you messed up the doc test in commit 4f26871 and are now changing it back in commit 8d8a2ea.
So I see nothing wrong here with the invariants code.
comment:27 in reply to: ↑ 26 Changed 4 years ago by
Replying to bhutz:
Actually, it looks like you messed up the doc test in commit 4f26871 and are now changing it back in commit 8d8a2ea.
So I see nothing wrong here with the invariants code.
My bad. Thanks for having a look!
comment:28 Changed 4 years ago by
 Keywords days88 IMA coding sprints added
 Milestone changed from sage8.0 to sage8.1
 Status changed from needs_review to positive_review
Thanks.
LGTM.
comment:29 Changed 4 years ago by
 Branch changed from u/vdelecroix/23402 to 8d8a2ea708b6fbb8aaa22f5fec07d6bbc4a96d9a
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
23388: faster floor for nf element
23402: faster hash for nf elements