faster hash of number field elements

[videlec]

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

Depends on #23388

CC: @bhutz

Component: number fields

Keywords: days88, IMA coding sprints

Author: Vincent Delecroix

Branch/Commit: 8d8a2ea

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/23402

[videlec]

Author: Vincent Delecroix

[videlec]

Commit: 2873d21

[videlec]

New commits:

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

[videlec]

Branch: u/vdelecroix/23402

[videlec]

Dependencies: #23388

[tscrim]

comment:3

Where did the two magic numbers come from? Also, why is one is hex and the other in decimal?

[videlec]

comment:4

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.

[videlec]

comment:5

... bad idea (got stupid collisions)

[sagetrac-git]

Changed commit from 2873d21 to 862184f

[sagetrac-git]

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

862184f

23402: faster hash for nf elements

[videlec]

comment:7

More coherent version in 8124ba5 where both values are:

• 63 bits
• documented
• in decimal notation

[sagetrac-git]

Changed commit from 862184f to 8124ba5

[sagetrac-git]

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

8124ba5

23402: faster hash for nf elements

[tscrim]

comment:9

Okay, thanks. LGTM.

[tscrim]

Reviewer: Travis Scrimshaw

[videlec]

comment:10

Changing the hash is changing the order of display in sets... some doctests break.

[sagetrac-git]

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

4778057

23402: fix doctests23402: fix doctests

[sagetrac-git]

Changed commit from 8124ba5 to 4778057

[sagetrac-git]

Changed commit from 4778057 to 9de6f18

[videlec]

comment:17

Indeed... 3 collisions in 32 bits! Probabilistically, we should not see any collision before a sample of size 2¹⁶ = sqrt(2³²).

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 9de6f18 to ab28ce8

[videlec]

comment:19

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

[tscrim]

comment:20

Doctest order failures due to the new hash. See patchbot report.

[sagetrac-git]

Changed commit from ab28ce8 to 9d0329f

[sagetrac-git]

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

[videlec]

comment:22

(rebased with a new commit to fix the doctests)

[sagetrac-git]

Changed commit from 9d0329f to 8d8a2ea

[sagetrac-git]

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

8d8a2ea

23402: one more doctest fix

[videlec]

comment:24

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

[videlec]

comment:25

@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]

[bhutz]

comment:26

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.

[videlec]

comment:27

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!

[tscrim]

Changed keywords from none to days88, IMA coding sprints

[tscrim]

comment:28

Thanks.

LGTM.

[vbraun]

Changed branch from u/vdelecroix/23402 to 8d8a2ea