Huge speed up for hash of quadratic number field elements

[videlec]

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

CC: @nathanncohen

Component: number fields

Author: Vincent Delecroix

Branch/Commit: bee81ef

Reviewer: Nathann Cohen

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

[videlec]

Branch: u/vdelecroix/18215

[videlec]

Commit: 2862b49

[videlec]

New commits:

2862b49

Trac 18215: Faster hash for quadratic number fields

[jdemeyer]

comment:2

Is there a reason why the hash should be the same as the one for the polynomial?

[videlec]

comment:3

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?

[sagetrac-git]

Changed commit from 2862b49 to 3ec20b4

[sagetrac-git]

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

3ec20b4

Trac 18215: Faster hash for quadratic number fields

[videlec]

comment:7

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

[nathanncohen]

comment:8

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.

[videlec]

comment:9

Replying to @nathanncohen:

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.

[nathanncohen]

Reviewer: Nathann Cohen

[videlec]

comment:11

Thanks Nathann!

[sagetrac-git]

Changed commit from 3ec20b4 to bee81ef

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

bee81ef

Trac 18215: fix a failing doctest

[vbraun]

Changed branch from u/vdelecroix/18215 to bee81ef