inconsistent integer hashing

[robertwb]

sage: z = 18446462603027742720
sage: hash(z)
66912258
sage: hash(int(z))
-131071
sage: hash(long(z))
-131071

This causes problems with looking up values in hashtables...

Component: basic arithmetic

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

[craigcitro]

comment:1

This was ugly. It turns out that we were shifting an int to the right by 45 bits on a 32 bit machine, which one might think would result in zero, but in fact shifts to the right by (45%32) = 13 bits.

The attached patch fixes this, and adds some doctests.

[robertwb]

comment:2

Excellent. I haven't been able to break it, and the code (and comment) look good.

[sagetrac-mabshoff]

comment:3

This is broken on 64 bit linux:

sage -t -long "devel/sage/sage/rings/integer.pyx"           
**********************************************************************
File "/scratch/mabshoff/sage-3.3.alpha2/devel/sage/sage/rings/integer.pyx", line 2085:
    sage: n = -920390823904823094890238490238484; n.__hash__()
Expected:
    6874330978542788722   
Got:
    6917515397235318898
**********************************************************************
File "/scratch/mabshoff/sage-3.3.alpha2/devel/sage/sage/rings/integer.pyx", line 2101:
    sage: hash(n)
Expected:
    -9223372036854767616      
Got:
    8192
**********************************************************************
File "/scratch/mabshoff/sage-3.3.alpha2/devel/sage/sage/rings/integer.pyx", line 2104:
    sage: hash(n) == hash(int(n))
Expected:
    True
Got:
    False
**********************************************************************

[robertwb]

comment:4

Darn :(. The first two may be OK (we need to see what hash(int(n)) is, but the second one is a problem.

[craigcitro]

Attachment: trac-4957.patch.gz

[craigcitro]

comment:5

Ok, I fixed it. It turns out it was some sloppy C coding on my part: I really wanted sizeof(mp_limb_t) instead of sizeof(int).

[robertwb]

comment:6

I bet this is the right fix, could you re-run the tests on a 64 bit machine?

[robertwb]

comment:7

That does the trick on sage.math

[sagetrac-mabshoff]

comment:8

Merged in Sage 3.3.alpha3.

Cheers,

Michael