Comparing complex numbers
Nils Bruin
"<", but from a mathematical point of view the following makes me
cringe:
sage: C.<i>=ComplexField()
sage: 1+i > 1-i
True
sage: 1+i < 1-i
False
Imagine being shown this by a student after you have explained your
complex variables class that complex numbers do NOT have an ordering.
Convincing the student that Sage is being non-mathematical here
requires some work, because sage's choice of comparing first the real
part and then the imaginary part is actually quite a smart one.
Would it break Python too much if comparison would simply throw an
exception in these cases?
Fredrik Johansson
>
> Would it break Python too much if comparison would simply throw an
> exception in these cases?
Hardly, considering that this is what Python itself does:
>>> 1+1j > 1-1j
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers
Fredrik
Alfredo Portes
William Stein
Note by the way that this has consequences:
>>> v = [1+1j , 1-1j]
sage: v.sort()
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/Users/was/<ipython console> in <module>()
TypeError: no ordering relation is defined for complex numbers
However, these aren't too hard to deal with:
>>> v.sort( lambda x,y: cmp(str(x),str(y)) )
>>> v
[(1+1j), (1-1j)]
So, for places in our code -- e.g., roots of polynomials -- where
we want the result "sorted" for consistency of output, we could
just have a bunch of "pseudo comparison" functions.
William
Nils Bruin
wrote:
> Hardly, considering that this is what Python itself does:
>
> >>> 1+1j > 1-1j
>
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> TypeError: no ordering relation is defined for complex numbers
think Sage should only allow "<" comparison when it has a mathematical
footing. See also:
http://trac.sagemath.org/sage_trac/ticket/3936
William Stein
>
> On Aug 23, 1:00 pm, "Fredrik Johansson" <fredrik.johans...@gmail.com>
> wrote:
>
>> Hardly, considering that this is what Python itself does:
>>
>> >>> 1+1j > 1-1j
>>
>> Traceback (most recent call last):
>> File "<stdin>", line 1, in <module>
>> TypeError: no ordering relation is defined for complex numbers
>
> Ah, well, if python itself already has uncomparable objects, then I
> think Sage should only allow "<" comparison when it has a mathematical
> footing.
Did you read through the article Alfredo Portes posted, which
also explains some of the gotchas and subtleties of disallowing
comparisons? I'm curious what you thought of it.
> See also:
>
> http://trac.sagemath.org/sage_trac/ticket/3936
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
David Philp
I think what you are suggesting is roughly how Mathematica does it.
Details might help:
Mathematica provides two functions, "Less" and "Order". "<" is an
infix notation for Less.
1+i < 2+i throws an exception ("invalid comparison with 1+i
attempted"). Order[a, b] is the same idea as python's cmp, except
that Order doesn't use "<", but some arbitrary ("canonical")
ordering. (To avoid weirdness, small numbers precede bigger numbers).
Sort[ list ] uses Order to perform the sort. This always works. List
can contain any thing, including numbers, plots, etc, and they will
always come sorted in the same order.
Sort[ list, fn ] uses fn to perform the sort. If you provide fn =
Less, and list contains complex numbers, exceptions are thrown.
Order is generally a pretty useful basic function, it would be
worthwhile providing something like it.
D
Carl Witty
> 1+i < 2+i throws an exception ("invalid comparison with 1+i
> attempted"). Order[a, b] is the same idea as python's cmp, except
> that Order doesn't use "<", but some arbitrary ("canonical")
> ordering. (To avoid weirdness, small numbers precede bigger numbers).
>
> Sort[ list ] uses Order to perform the sort. This always works. List
> can contain any thing, including numbers, plots, etc, and they will
> always come sorted in the same order.
> worthwhile providing something like it.
separately, so we could leave cmp() total and still make < partial.
Carl
Nils Bruin
> Did you read through the article Alfredo Portes posted, which
> also explains some of the gotchas and subtleties of disallowing
> comparisons? I'm curious what you thought of it.
The one example that David Mertz gives in favour of universal ordering
is sorting, which completely hinges on transitivity of "<". As it
stands at the moment with 1 < None < int(0), this is already violated.
That means that any algorithm based on sorting can fail in
unpredictable ways.
In the article he already mentions that one of the main reasons for
sorting - doing quick membership tests - can be avoided by using sets
and hashing instead (which should be a superior solution anyway?). And
the reality in Python is that "<" is not universal anymore anyway.
The examples he gives that (1+1j) < "a" but that (1+1j) < 0 raises an
exception are just hairraisingly inconsistent. I would hope that the
former will lead to an exception in some future version of python as
well.
I would say that the goal of Sage - being a viable alternative to
various Ms - means that Sage should stay as close to the mathematical
meaning of things as possible (without creating a strange dialect of
python) rather than allow tricks convenient to programmers.
Concerning Carl Witty's argument for universal cmp():
It seems hard to me to ensure transitivity for a universal cmp() if
you want to depart "<" from "cmp()", plus it will be a big gotcha for
beginning/intermediate sage programmers if cmp and "<" can behave
differently. Is it really so bad to do a
L.sort(compare_function=compare_memory_addresses)
or
L.sort(compare_function=compare_hash_values)
when you absolutely want to sort anything at all? At least it makes a
clear statement "yes, I want to sort using a completely arbitrary
order that is at least consistent on short timescales". I imagine such
code could actually be quite efficient.
So in short, the article that Alfredo posted convinced me even more
that sage would benefit from taking a hard line on comparison.
William Stein
> On Aug 23, 1:27 pm, "William Stein" <wst...@gmail.com> wrote:
>
>> Did you read through the article Alfredo Portes posted, which
>> also explains some of the gotchas and subtleties of disallowing
>> comparisons? I'm curious what you thought of it.
>
> At the very least, "<" should be transitive wherever it is allowed.
> The one example that David Mertz gives in favour of universal ordering
> is sorting, which completely hinges on transitivity of "<". As it
> stands at the moment with 1 < None < int(0), this is already violated.
> That means that any algorithm based on sorting can fail in
> unpredictable ways.
[...]
Just as another data point, since I happened to see it when reading
source code, in the Ginac library (http://www.ginac.de) we find this comment:
/** This method establishes a canonical order on all numbers. For complex
* numbers this is not possible in a mathematically consistent way
but we need
* to establish some order and it ought to be fast. So we simply define it
* to be compatible with our method csgn.
*
* @return csgn(*this-other)
* @see numeric::csgn() */
I'm not making or suggesting any conclusions -- just adding another data point.
William
Simon King
On Aug 24, 2:59 am, Carl Witty <carl.wi...@gmail.com> wrote:
> We can just use cmp(), if we want. Python lets you define < and cmp()
> separately, so we could leave cmp() total and still make < partial.
command line?
I guess the expected interpretation of "<" is the mathematical one --
hence, if there is no common parent of a and b or if that common
parent is not an ordered algebraic structure then the user may be
unhappy if no TypeError or ArithmeticError is raised.
On the other hand, in programming one sometimes needs a total order
and can ignore algebra (e.g., sorting).
Therefore, Carl's proposal seems reasonable to me. It takes into
account both requirements.
Cheers
Simon
Kurt
On Aug 24, 12:02 pm, "William Stein" <wst...@gmail.com> wrote:
>[...]
> Just as another data point, since I happened to see it when reading
> source code, in the Ginac library (http://www.ginac.de) we find this comment:
>
> /** This method establishes a canonical order on all numbers. For complex
> * numbers this is not possible in a mathematically consistent way
> but we need
> * to establish some order and it ought to be fast. So we simply define it
> * to be compatible with our method csgn.
/pedantic ON
It is, of course, possible to establish a total ordering on the
complex numbers.
In many ways. So it is not true to say otherwise.
The issue is that cryptic phrase, "in a mathematically consistent
way".
If all you are interested in is, say, topology, then every total
ordering gives you
an order topology on the set. Nothing mathematically inconsistent in
this context.
What is usually meant by the phrase is that one cannot have a total
ordering
on the complex numbers that simultaneously preserves the full range of
cherished properties,
including the algebraic ones, that we know and love about the usual
ordering of the reals.
For example, that the order on the complex numbers be an extension of
the natural ordering of the reals,
that ((0 < a) and (0 < b)) implies (0 < ab), that the order topology
be the same as that induced by the usual Euclidean metric, etc.
/pedantic OFF
Whether this last context is the appropriate one to drive the issue of
whether there should be a default order implemented for complex
numbers in Sage (or even Python, for that matter) is debatable. IMHO,
if it is useful to programming to have a default comparison, such as
for sorting lists, then I think it would be OK to have one. Document
what it does, and if necessary, explain to your students the reason
for it.