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: sage-8.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:

Status badges

Description (last modified by vdelecroix)

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 vdelecroix

  • Authors set to Vincent Delecroix
  • Branch set to u/vdelecroix/23402
  • Commit set to 2873d21f869dabd15a7df049dfa2262706b74893
  • Dependencies set to #23388
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

0146c8623388: faster floor for nf element
2873d2123402: faster hash for nf elements

comment:2 Changed 4 years ago by vdelecroix

  • Description modified (diff)

comment:3 Changed 4 years ago by tscrim

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 vdelecroix

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.

Last edited 4 years ago by vdelecroix (previous) (diff)

comment:5 Changed 4 years ago by vdelecroix

... bad idea (got stupid collisions)

comment:6 Changed 4 years ago by git

  • Commit changed from 2873d21f869dabd15a7df049dfa2262706b74893 to 862184f6f277732287d2ffdf8aa06db8a94a7269

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

862184f23402: faster hash for nf elements

comment:7 Changed 4 years ago by vdelecroix

More coherent version in 8124ba5 where both values are:

  • 63 bits
  • documented
  • in decimal notation
Last edited 4 years ago by vdelecroix (previous) (diff)

comment:8 Changed 4 years ago by git

  • Commit changed from 862184f6f277732287d2ffdf8aa06db8a94a7269 to 8124ba562387db04596077ba178d1fca154d0ab3

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

8124ba523402: faster hash for nf elements

comment:9 Changed 4 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Okay, thanks. LGTM.

comment:10 Changed 4 years ago by vdelecroix

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

  • Commit changed from 8124ba562387db04596077ba178d1fca154d0ab3 to 47780570267859ae89fc66341eea97e9ead7fd2d

Branch pushed to git repo; I updated commit sha1. New commits:

477805723402: fix doctests23402: fix doctests

comment:12 Changed 4 years ago by git

  • Commit changed from 47780570267859ae89fc66341eea97e9ead7fd2d to 9de6f1881aaa2160081585490d70b698bfd5cbdf

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

9de6f1823402: fix doctests

comment:13 Changed 4 years ago by vdelecroix

  • Description modified (diff)

comment:14 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Now tests do pass.

comment:15 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:16 Changed 4 years ago by vbraun

Fails on 32-bit:

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 vdelecroix

Indeed... 3 collisions in 32 bits! Probabilistically, we should not see any collision before a sample of size 216 = sqrt(232).

Last edited 4 years ago by vdelecroix (previous) (diff)

comment:18 Changed 4 years ago by git

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

ab28ce823402: better magic numbers avoiding small collisions

comment:19 Changed 4 years ago by vdelecroix

needs review (no collision on the 18 first bits which is more than enough for 32 bits)

comment:20 Changed 4 years ago by tscrim

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

  • Commit changed from ab28ce8a7d7dd60a1b426b16462f53645cee5f4f to 9d0329f8d1440e53a3195cd24e9fdeb518ec9775

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

0361ee123402: faster hash for nf elements
4f2687123402: fix doctests
dd1406b23402: better magic numbers avoiding small collisions
9d0329f23402: more doctest fixes

comment:22 Changed 4 years ago by vdelecroix

  • Status changed from needs_work to needs_review

(rebased with a new commit to fix the doctests)

comment:23 Changed 4 years ago by git

  • Commit changed from 9d0329f8d1440e53a3195cd24e9fdeb518ec9775 to 8d8a2ea708b6fbb8aaa22f5fec07d6bbc4a96d9a

Branch pushed to git repo; I updated commit sha1. New commits:

8d8a2ea23402: one more doctest fix

comment:24 Changed 4 years ago by vdelecroix

The second doctest change in 8d8a2ea708 looks fishy. Actually, the version after my changes looks better!!

comment:25 Changed 4 years ago by vdelecroix

  • 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 follow-up: Changed 4 years ago by 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.

comment:27 in reply to: ↑ 26 Changed 4 years ago by vdelecroix

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 tscrim

  • Keywords days88 IMA coding sprints added
  • Milestone changed from sage-8.0 to sage-8.1
  • Status changed from needs_review to positive_review

Thanks.

LGTM.

comment:29 Changed 4 years ago by vbraun

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