Opened 13 years ago

Closed 13 years ago

#4957 closed defect (fixed)

[with patch, positive review] inconsistent integer hashing

Reported by: robertwb Owned by: craigcitro
Priority: critical Milestone: sage-3.3
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description 

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

Attachments (1)

trac-4957.patch​ (1.8 KB) - added by craigcitro 13 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 13 years ago by craigcitro

  • Milestone changed from sage-3.4.1 to sage-3.3
  • Owner changed from somebody to craigcitro
  • Status changed from new to assigned
  • Summary changed from inconsistent integer hashing to [with patch, needs review] inconsistent integer hashing

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.

comment:2 Changed 13 years ago by robertwb

  • Summary changed from [with patch, needs review] inconsistent integer hashing to [with patch, positive review] inconsistent integer hashing

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

comment:3 Changed 13 years ago by mabshoff

  • Summary changed from [with patch, positive review] inconsistent integer hashing to [with patch, needs work] inconsistent integer hashing

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

comment:4 Changed 13 years ago by robertwb

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

Changed 13 years ago by craigcitro

comment:5 Changed 13 years ago by craigcitro

  • Summary changed from [with patch, needs work] inconsistent integer hashing to [with patch, needs review] inconsistent integer hashing

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

comment:6 Changed 13 years ago by robertwb

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

comment:7 Changed 13 years ago by robertwb

  • Summary changed from [with patch, needs review] inconsistent integer hashing to [with patch, positive review] inconsistent integer hashing

That does the trick on sage.math

comment:8 Changed 13 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from assigned to closed

Merged in Sage 3.3.alpha3.

Cheers,

Michael

Note: See TracTickets for help on using tickets.