Opened 5 years ago

Closed 5 years ago

faster hash of number field elements

Reported by: Owned by: vdelecroix major sage-8.1 number fields days88, IMA coding sprints bhutz Vincent Delecroix Travis Scrimshaw N/A 8d8a2ea 8d8a2ea708b6fbb8aaa22f5fec07d6bbc4a96d9a #23388

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))
```

comment:1 Changed 5 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:

 ​0146c86 `23388: faster floor for nf element` ​2873d21 `23402: faster hash for nf elements`

comment:2 Changed 5 years ago by vdelecroix

• Description modified (diff)

comment:3 Changed 5 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 5 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 5 years ago by vdelecroix (previous) (diff)

comment:5 Changed 5 years ago by vdelecroix

... bad idea (got stupid collisions)

comment:6 Changed 5 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:

 ​862184f `23402: faster hash for nf elements`

comment:7 Changed 5 years ago by vdelecroix

More coherent version in `8124ba5` where both values are:

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

comment:8 Changed 5 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:

 ​8124ba5 `23402: faster hash for nf elements`

comment:9 Changed 5 years ago by tscrim

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

Okay, thanks. LGTM.

comment:10 Changed 5 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 5 years ago by git

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

 ​9de6f18 `23402: fix doctests`

comment:13 Changed 5 years ago by vdelecroix

• Description modified (diff)

comment:14 Changed 5 years ago by vdelecroix

• Status changed from needs_work to needs_review

Now tests do pass.

comment:15 Changed 5 years ago by tscrim

• Status changed from needs_review to positive_review

comment:16 Changed 5 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 of   9 in sage.rings.number_field.number_field_element.NumberFieldElement.__hash__
[1084 tests, 1 failure, 827.34 s]
```

comment:17 Changed 5 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 5 years ago by vdelecroix (previous) (diff)

comment:18 Changed 5 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:

 ​ab28ce8 `23402: better magic numbers avoiding small collisions`

comment:19 Changed 5 years ago by vdelecroix

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

comment:20 Changed 5 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 5 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:

 ​0361ee1 `23402: faster hash for nf elements` ​4f26871 `23402: fix doctests` ​dd1406b `23402: better magic numbers avoiding small collisions` ​9d0329f `23402: more doctest fixes`

comment:22 Changed 5 years ago by vdelecroix

• Status changed from needs_work to needs_review

(rebased with a new commit to fix the doctests)

comment:23 Changed 5 years ago by git

• 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 5 years ago by vdelecroix

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

comment:25 Changed 5 years ago by vdelecroix

@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: ↓ 27 Changed 5 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 5 years ago by vdelecroix

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 5 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 5 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.