http://codereview.appspot.com/660042/diff/19001/11011 File Objects/longobject.c (right): http://codereview.appspot.com/660042/diff/19001/11011#newcode2577 Objects/longobject.c:2577: this multiplies by 2**PyLong_SHIFT modulo 2**31 - 1. */ ...

13 years, 6 months ago
(2010-03-23 11:56:56 UTC)
#2

http://codereview.appspot.com/660042/diff/19001/11011
File Objects/longobject.c (right):
http://codereview.appspot.com/660042/diff/19001/11011#newcode2577
Objects/longobject.c:2577: this multiplies by 2**PyLong_SHIFT modulo 2**31 - 1.
*/
On 2010/03/21 17:04:48, GvR wrote:
> Can't say I understand all this. I guess my number theory is lacking; I don't
> get how you can compute modulo a prime by using a shift. ;-(
I'll add some explanatory comments. (That 2**31 - 1 needs to be changed to
_PyHASH_MASK, too.) The idea's something like the following: suppose 0 <= x <
2**31; you want to multiply x by 2**15 and then reduce the result modulo
2**31-1. Let y be the portion of x that's shifted out of the top of the
original 31 bits, so that x * 2**15 = y * 2**31 + z for some z. Then since
2**31 reduces to 1 modulo 2**31-1, y*2**31 reduces to y. So x*2**15 reduces to
y + z. IOW, you just take the 15 bits that were shifted out of the top
(y*2**31) and add them back in at the bottom (as y), so you end up with a
rotation.
http://codereview.appspot.com/660042/diff/19001/11011#newcode2582
Objects/longobject.c:2582: incrementing. This preserves the value modulo
On 2010/03/21 17:04:48, GvR wrote:
> incrementing? This comment seems outdated now.
Agreed. I'll remove it.
http://codereview.appspot.com/660042/diff/19001/11009
File Objects/object.c (right):
http://codereview.appspot.com/660042/diff/19001/11009#newcode667
Objects/object.c:667: 1 + reduce(x-1) if x > 0
On reflection, I think this could be simplified to just reduce(x). (So it
reduces to 0, ... P-1 rather than 1, ... P). The +-1 aren't necessary, and just
make it that little bit harder and more error-prone for 3rd party hashes.
FWIW, the (minor) advantages of the extra +-1 were:
- it means that hash(x) == 0 iff x == 0, hash(x) > 0 for
all x > 0 and hash(x) < 0 for x < 0. Which is cute,
but not really especially useful.
- it retains the property that hash(x) == x for all
(Python 2.x, short) ints x, with two exceptions
(-1 and -2**31). Without the +-1 above, there are 4
exceptions (-1, -2**31+1, -2**31 and 2**31-1), so makes
the implementation for short ints slightly cleaner.
Since this isn't likely to go into 2.x anyway, that's
not much of an advantage. Also, this doesn't help on
64-bit platforms, where we're using 61 bits rather than
63.
http://codereview.appspot.com/660042/diff/19001/11010
File Objects/typeobject.c (right):
http://codereview.appspot.com/660042/diff/19001/11010#newcode4936
Objects/typeobject.c:4936: h = PyLong_AsLongAndOverflow(res, &overflow);
There's a missing exception check on the result of PyLong_AsLongAndOverflow
here.
http://codereview.appspot.com/660042/diff/19001/11010#newcode4938
Objects/typeobject.c:4938: if (PyLong_Check(res))
Need to check what the correct behaviour is when the __index__ method returns
something that's not a Python integer; add tests for this if they don't already
exist.
http://codereview.appspot.com/660042/diff/19001/11007
File Python/sysmodule.c (right):
http://codereview.appspot.com/660042/diff/19001/11007#newcode578
Python/sysmodule.c:578: A private struct sequence providing parameters used for
computing\n\
On 2010/03/21 17:04:48, GvR wrote:
> Why private? I'm sure 3rd party number implementations will want to consult
this
> too. It should be a public API.
Okay, will make it public. That gives me greater motivation to make sure that I
get it absolutely right first time. :)

http://codereview.appspot.com/660042/diff/63001/64009 File Doc/library/stdtypes.rst (right): http://codereview.appspot.com/660042/diff/63001/64009#newcode631 Doc/library/stdtypes.rst:631: - If ``x = m / n`` is a ...

13 years, 4 months ago
(2010-05-23 10:46:32 UTC)
#6

Issue 660042: Compatible numeric hashes
Created 13 years, 6 months ago by dickinsm
Modified 13 years, 4 months ago
Reviewers: GvR, Christophe Simonis
Base URL: http://svn.python.org/view/*checkout*/python/branches/py3k/
Comments: 14