py3: Fix hash function of Integer

[gh-mwageringel]

This ticket fixes an issue in sage.libs.gmp.pylong.mpz_pythonhash, the hash function for Integer, and resolves the Python 3 doctest failures in sage/rings/integer.pyx.

More precisely, the implementation of mpz_pythonhash is using the fact that y <= modulus, as explained in the comment

        # Safely compute h = (h + y) % modulus knowing that h < modulus
        # and y <= modulus

However, this assumption is not always correct, as y is the sum of up to three numbers. For example, this fails in

sage: hash(2^64 - 1), hash(int(2^64 - 1))
(2305843009213693958, 7)

[gh-mwageringel]

I have not had the chance to test this with Python 3 on a 32-bit machine. Instead, I just computed the 32-bit hashes in the doctests using a modulus of 2^31 - 1. Could someone with access to a 32-bit machine confirm or correct these, please?

---

New commits:

​ba487ec

28112: py3: fix Integer hash and doctests

[jdemeyer]

Replying to gh-mwageringel:

I have not had the chance to test this with Python 3 on a 32-bit machine.

Do we really need the exact values in the docstring? Wouldn't it be sufficient to mark those tests with # random? The only thing really that matters is that hash(n) == hash(int(n)).

[jdemeyer]

Given that y is less than 2 * modulus, it is more efficient to do

if y > modulus:
    y -= modulus

(Note that the condition y > modulus instead of y >= modulus is intentional as it generates better code).

[git]

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

​8770241

28112: py3: fix Integer hash and doctests

[gh-mwageringel]

Replying to jdemeyer:

Do we really need the exact values in the docstring? Wouldn't it be sufficient to mark those tests with # random? The only thing really that matters is that hash(n) == hash(int(n)).

I agree. I updated the tests accordingly, keeping just the 64-bit Python 3 output. At some point, this should still be tested with 32-bit, though.

I also applied the other suggested change. Thanks for the feedback.

[jhpalmieri]

I would prefer not to use long in doctests, since it is not supported in Python 3. The only reason it works in Sage now is because of a hack that converts long to int when using Python 3. Maybe instead separate doctests?

sage: n.__hash__() == hash(long(n)) # py2
True
sage: n.__hash__() == hash(n) # py3
True

[gh-mwageringel]

Replying to jhpalmieri:

I would prefer not to use long in doctests, since it is not supported in Python 3. The only reason it works in Sage now is because of a hack that converts long to int when using Python 3. Maybe instead separate doctests?

Good point. Instead of having separate doctests, I think it is preferable to replace long(n) by int(n) which should work in both Python 2 and 3. In Python 2, it will still return a long if the number is too large.

[git]

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

​b1efe82

28112: py3: replace long by int in Integer doctests

[jdemeyer]

One final nitpick: this comment # This is safe, since y <= 2 * modulus < 2 ^ limb_bits. is not clear, I don't know what you're trying to say with it. I would say something like

# At this point, y < 2 * modulus but we need y <= modulus
# We use > instead of >= on the line below because it
# generates more efficient code

[gh-mwageringel]

Replying to jdemeyer:

One final nitpick: this comment # This is safe, since y <= 2 * modulus < 2 ^ limb_bits. is not clear, I don't know what you're trying to say with it.

What I was trying to emphasize is that y did not overflow which is important for the comparison to work. I will rephrase it to make this clearer.

Before adding a comment about efficiency, I would like to understand better why this is more efficient and why it is important. Could you explain this please? Is it because it saves a subtraction occasionally, or are < comparisons generally faster than <=, or maybe would it help the compiler do branch elimination?

[jhpalmieri]

Is it easy to also address this? In Sage + Python 2:

sage: all(hash(2^n-1)==hash(SR(2^n-1)) for n in range(60, 100))
True

In Sage + Python 3:

sage: hash(2^60-1) == hash(SR(2^60-1))
True
sage: hash(2^61-1) == hash(SR(2^61-1))
False

[chapoton]

Let us keep the SR issue for elsewhere. The branch looks good to me.

Jeroen, do you approve ?

[jdemeyer]

The SR issue might be upstream in Pynac.

[jdemeyer]

Replying to gh-mwageringel:

I would like to understand better why this is more efficient and why it is important.

It's certainly not important. It's just that, out of two possible alternatives, the > alternative is slightly faster.

Could you explain this please?

I don't think that there is a fundamental reason. It's just that the compiler generates more efficient instructions for the > variant.

[jdemeyer]

Replying to chapoton:

Jeroen, do you approve ?

Yes, I approve. I'm just waiting for the rewording of the comment.

[git]

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

​b13f7f8

28112: reword a comment in hash function

[gh-mwageringel]

Replying to jdemeyer:

Replying to gh-mwageringel:

I would like to understand better why this is more efficient and why it is important.

It's certainly not important. It's just that, out of two possible alternatives, the > alternative is slightly faster.

Could you explain this please?

I don't think that there is a fundamental reason. It's just that the compiler generates more efficient instructions for the > variant.

Thank you for explaining. I changed the comment. It should be fine now.

[chapoton]

I am setting to positive. Jeroen, if you do not agree, then undo