I've just discovered that integer-to-complex comparisons are broken, in all versions of Python that I've tested.  It looks as though the integer is first converted to a complex number, and then the two complex numbers are compared.  That's not correct, and it's contrary to what happens for floats, where there's special handling in place to make sure that exact values are compared.  This leads to loss of transitivity of equality:

>>> n = 2**53+1
[51529 refs]
>>> float(n) == complex(n)  # expect True
True
[51531 refs]
>>> n == float(n)           # expect False
False
[51531 refs]
>>> n == complex(n)         # expect False, but Python returns True
True
[51531 refs]

Apparently the SAGE folks noticed this some time ago, but AFAICT didn't report it as a bug. See http://www.mail-archive.com/sage-devel@googlegroups.com/msg20891.html

For a complex number z and an integer i, 'z == i' should be exactly equivalent to 'z.real == i and z.imag == 0.0'.

Right thread, wrong message.  That should have been:

http://www.mail-archive.com/sage-devel@googlegroups.com/msg20839.html

More fun arising from the current complex comparison implementation:  usually you can put a complex number and an integer into the same set:

>>> {1, 2j}  # (Python 3 code)
{1, 2j}
>>> s = {10**1000, 2j}  # huge integers no problem

But if you happen to pick the wrong combination....

>>> x, n = 9.3 + 0j, 10**300*(2**64-1)+hash(9.3)
>>> x
(9.3+0j)
>>> n
18446744073709551615000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002107349606
>>> {x, n}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to float

> For a complex number z and an integer i, 'z == i' should be exactly 
> equivalent to 'z.real == i and z.imag == 0.0'.

Like you mentioned before a lot of care is taken in 'floatobject.c' to ensure that the comparison is robust.  Would it be a good approach to leverage that work?

I have attached a patch with that idea.  If it seems reasonable, then I can clean it up and add more tests.  I created the patch for py3k.  I think the 2.x changes will be slightly different due to the coercion aspects.

One of the unit tests ('test_complex.test_richcompare') explicitly checks for the overflow.  However, the approach of just having the comparison return 'False' in these cases is more robust.  Is there any use case for explicitly notifying of overflow with comparisons?  It seems like more of an implementation artifact to me...

> Like you mentioned before a lot of care is taken in 'floatobject.c' to > ensure that the comparison is robust.  Would it be a good approach to
> leverage that work?

Absolutely, yes!  I was thinking of moving that chunk of code out of float_richcompare and into something like _PyLong_CompareWithDouble (in Objects/longobject.c).  Then it can be used by both float_richcompare and complex_richcompare.

Hmm.  This works well for py3k, but not so well for trunk, where we have to deal with plain 'int's as well.

I'd definitely like this fixed in 2.7 and 3.2:  it's horrible behaviour.  I'm still wondering about 2.6 and 3.1.  I just discovered that there's actually a test for part of this behaviour (first line of test_richcompare in test_complex.py):

    self.assertRaises(OverflowError, complex.__eq__, 1+1j, 1<<10000)

Nevertheless, I still maintain that this is wrong:  raising an exception in __eq__ is always a dangerous thing to do for hashable objects, since it leads to confusing behavour like this:
Python 2.5.1 (r251:54863, Dec 6 2008, 10:49:39)
[GCC 4.2.1 (SUSE Linux)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> s = set([2**1024])
>>> s.add(complex(0))
>>> s.add(complex(2))
>>> s.add(complex(1))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to float

Thinking about it, I still like the _PyLong_CompareWithDouble plan even for trunk:  there's a precedent for some PyLong methods working with plain ints as well as for longs.  See e.g. PyLong_AsLongLong and friends.

[Meador]
> One of the unit tests ('test_complex.test_richcompare') explicitly
> checks for the overflow.

[Mark]
> I just discovered that there's actually a test for part of this
> behaviour

D'oh!  Next time I'll read your whole message before responding to the first bit.  Apologies.

From a brief glance, the approach in your patch looks fine to me.  I'll have a proper look at it later today.

Okay, this patch looks fine to me for py3k.  More tests would be great, but I don't see much other cleaning up that needs doing.

Just one thing:  I'd make the 'i.imag == 0.0' check earlier, so that the potentially expensive long-to-float check can be avoided where appropriate.

I'd also move the 'op != Py_EQ && op != Py_NE' check before the first TO_COMPLEX, though I realize that this is orthogonal to the issue under discussion;  the definition seems cleaner that way, though I don't think it makes any difference to the behaviour.

Thanks for the review.  I incorporated the check re-orderings.

I am also writing more tests.  Which already exposed a subtly that I was not expecting:


Python 3.2a0 (py3k:81284M, May 20 2010, 09:08:20) 
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> n = 2 ** 53
[37447 refs]
>>> complex(n + 2) == n + 2
True
[37457 refs]
>>> complex(n + 1) == n + 1
False
[37459 refs]
>>> complex(n + 3) == n + 3
False
[37460 refs]
>>> complex(n + 4) == n + 4
True
[37461 refs]
>>> 

It seems as if 'complex(n + delta) == n + delta' when 'delta' is even.

> It seems as if 'complex(n + delta) == n + delta' when 'delta' is even.

For n = 2**53, and 0 <= delta <= 2**53, this sounds about right;  the reason is that the numbers in the range [2**53, 2**54] that are exactly representable as an IEEE 754 double are the even numbers.  Similarly, the only numbers in [2**54, 2**55] that are representable are multiples of 4, etc.

Thanks for the updated patch;  I'll take a closer look tonight, and apply it if all looks good.

> Thanks for the updated patch;  I'll take a closer look tonight, and 
> apply it if all looks good.

I incorporated the changes locally and have not updated the patch yet.  I will update it later today.

D'oh!  Sorry.

No problem!  I have attached the updated patch.

I am starting on the 2.7 patch now.

2.7 patch attached.  The implementation is mostly the same as the 3.2 one, but there is one quirk.  Namely, 2.7 (and other 2.x's) has the following odd behavior:

   >>> 1j < None
   False
   >>> 1j < 1
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   TypeError: no ordering relation is defined for complex numbers

To perserve this behavior I had to do the type checks for 'int', 'long', 'complex', and 'float' at the beginning.  I tried 'PyNumber_Check' first, but it returns 1 for old-style classes since the number protocol is filled in for the 'instance' type.

py3k patch applied in r81397, with some tweaks:
 - fix reference leak (j wasn't being Py_DECREF'd in the long branch)
 - remove trailing whitespace
 - put 'else' and 'else if' on a new line following a closing brace
 - remove unnecessary NULL initializations
 - minor simplifications to long branch

Thanks!

Hmm.  The current Python 2.7 behaviour really is a mess.

Your patch removes the coercion entirely;  I'm not sure that's a good idea:  mightn't this change behaviour for user-defined classes with a __coerce__ method?  Maybe it would be better to just special-case ints and longs at the start of complex_richcompare, and then leave everything else more-or-less intact?

I'm beginning to wonder whether it's actually worth fixing this at all in 2.7.

> Hmm.  The current Python 2.7 behaviour really is a mess.

No doubt!

> Your patch removes the coercion entirely;  

Yeah, I know.  The funny thing about this is that according to the documentation [1]:

   "Arguments to rich comparison methods are never coerced."

> I'm not sure that's a good idea:  mightn't this change behaviour for 
> user-defined classes with a __coerce__ method?  Maybe it would be 
> better to just special-case ints and longs at the start of 
> complex_richcompare, and then leave everything else more-or-less 
> intact?

I will look into that today.

> I'm beginning to wonder whether it's actually worth fixing this at all > in 2.7.

:)

[1] http://docs.python.org/dev/reference/datamodel.html#basic-customization

> I'm not sure that's a good idea:  mightn't this change behaviour for 
> user-defined classes with a __coerce__ method?  Maybe it would be 
> better to just special-case ints and longs at the start of 
> complex_richcompare, and then leave everything else more-or-less 
> intact?

I looked into this more and agree.  I have attached a patch with the strategy that leaves the coercion intact.  Although, even with removing the coercion from the complex rich compare a user-defined __coerce__ is still called somewhere up in object.c.  It does not have the same behavior, though, e.g. __coerce__ is called, but the coerced args don't actually seem to be used in the comparison as they are in the explicit coerce in the complex object rich compare.

Somewhat of topic, but the comparison rules in 2.7 seems to be pretty inconsistent anyway (due to different behavior between new and old style classes):

motherbrain:trunk minge$ ./python.exe 
Python 2.7b2+ (trunk:81489M, May 29 2010, 09:44:06) 
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from itertools import product
[35627 refs]
>>> class T:
...    def __init__(self, x):
...       self.x = x
...    def __coerce__(self, other):
...       return (self.x, other)
... 
[35676 refs]
>>> class U(T, object):
...    def __init__(self, x):
...       super(U, self).__init__(x)
... 
[35723 refs]
>>> for tobj, value in product((T, U), (12, 12.0, complex(12.0))):
...    print tobj, " -> ", tobj(value) == value
... 
__main__.T  ->  True
__main__.T  ->  True
__main__.T  ->  True
<class '__main__.U'>  ->  True
<class '__main__.U'>  ->  False
<class '__main__.U'>  ->  True
[35740 refs]
>>> 


Given the complexities and subtleties of how comparison works in 2.7 I am a little hesitant to commit this change as well.

> Given the complexities and subtleties of how comparison works in 2.7
> I am a little hesitant to commit this change as well.

Understood.  Given how long we've lived with this behaviour in 2.x with no serious ill effects, it's very tempting to call this a "won't fix" for 2.7.  Really the coercion for complex types should have been removed at some point in the 2.x series, but it's too late for that now.

I'll take a look at the patch, though.

D'oh (again!)

[Mark]
> Really the coercion for complex types should have been removed at some
> point in the 2.x series

which of course, it was, in issue 5211.  And we should have caught the richcompare coercion in that issue.  So I apologise:  getting rid of the PyNumber_CoerceEx call was the right thing to do---we should have already done that in issue 5211.

Meador, I obviously haven't been thinking clearly about this.

Can you think of any reason that we shouldn't just copy the py3k implementation of complex_richcompare wholesale to trunk, with the single modification of replacing "if (PyLong_Check(w))" with "if (PyInt_Check(w) || PyLong_Check(w))"?

Okay, this is now fixed in trunk in r81610, using something closer to your original patch.

Thanks for all your help with this!

[Mark]
> Can you think of any reason that we shouldn't just copy the py3k 
> implementation ...

Not that I can think of.  Like you pointed out, we should have removed the  coercion from the rich comparison when fixing issue 5211.

> Thanks for all your help with this!

No problem!