bugGNU Octave - Bugs: bug #53013, Comparison of complex values 2

 
 

bug #53013: Comparison of complex values 2

Submitted by:  Michael Leitner <mleitner>
Submitted on:  Tue 30 Jan 2018 10:26:33 AM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Feature Request
Status:  None Assigned to:  None
Originator Name:  Open/Closed:  Open
Release:  4.2.1 Operating System:  Any

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Wed 31 Jan 2018 04:33:34 PM UTC, comment #6:

Actually you do no follow the ordering relationship, but you follow the sorting behaviour and deviate in the ordering relationship for being consistent. I would argue to do it the other way around. As Matlab has introduced switches to provide different sorting behaviours, it is then just a question of the default behaviour, where Octave would use a different one from Matlab so that sorting is consistent with ordering, but where the Matlab-compatible one could be requested easily. Thus, the degree of Matlab-compatibility would actually increase, in addition to the advantages I listed below.

Michael Leitner <mleitner>
Wed 31 Jan 2018 03:51:42 PM UTC, comment #5:

Unfortunately, we are not first and are bound by convention. Octave tries to be better than Matlab, but in some cases this is impossible. As you point out, definining the ordering relationship is arbitrary. We have an arbitrary choice by Matlab that we follow, but with an extra effort to be consistent about applying that choice.

Rik <rik5>
Project Administrator
Wed 31 Jan 2018 01:19:38 PM UTC, comment #4:

I want to maintain that, from the point of view of abstract mathematics, an order relation is just a binary relation with specific properties. That is, you could define your own order on, e.g., the real numbers which is equivalent to the conventional order with the exception that 5<=x for all positive x. That's a perfectly valid order, every sorting algorithm would happily sort your numbers according to this order (5 would come before 3, if both are in your input data, but that's consistent), and when you perform unique(), you would get exactly the same unique elements as with every other order relation (only in a different order, of course).

Naturally, there is not much reason why anyone would want to define such an order, because there is a natural order on the real numbers that follows from the order on the natural numbers (which naturally derives e.g. from the Peano construction) and that fulfills the laws how arithmetic operations affect order (e.g. a<b <=> a+c<b+c).

So it is possible to extend this order relation all the way from the naturals to the integers to the rationals to the real numbers, fulfilling said laws. However, it is not possible to extend it to the complex numbers: consider the law that a>b => (a* c>b* c if c>0 and a* c<b* c if c<0). Assume b=0, a=i and c=i. If we choose i>0, then we have a>0, but we have a* c=i* i=-1, which would also need to be greater than zero because c>0, which is a contradiction. See also https://proofwiki.org/wiki/Complex_Numbers_cannot_be_Totally_Ordered (where the title is misleading, there is just no ordering compatible with the multiplication law).

This is the reason that you often find "you cannot compare complex numbers for order" when you search for it. That's nonsense, of course you can, you could also define an order on the set {"Mickey", "Donald"} by setting "Mickey"<"Donald". Then you have a<b iff a=="Mickey" and b=="Donald". Octave wants to have a total order on the complex numbers, which I accept, because it allows for the standart implementation of unique() to directly work on complex values.

But for defining an order relation on the complex numbers, some choices have to be made, corresponding to which laws of ordering relations under arithmetic operations should be conserved. And, by the way: "total order" means that if a!=b we have either a<b or b<a. This is what we want, and by the way what Matlab according to their documentation does not do, as they compare only the real part (i.e., neither 1<1+1i nor 1>1+1i should evaluate to true, and of course also not 1==1+1i).

There seem to be two main contenders: either lexicographic order, where a<b == (real(a)<real(b))||((real(a)==real(b))&&(imag(a)<imag(b))), or abs-based order, where a<b == (abs(a)<abs(b))||((abs(a)==abs(b))&&(arg(a)<arg(b))).
I argue for lexicographic order, because this keeps the law a<b <=> a+c<b+c for any a,b,c, and further because it allows Octave's narrowing operation (that is, seeing a complex number with zero imaginary part as a real number) to be an order embedding https://en.wikipedia.org/wiki/Order_embedding. Indeed, there is even a trivial arxiv paper on it https://arxiv.org/abs/1003.4906 -- I did not check it in detail, but its main claims seem valid. Under abs-based order, this is no order embedding. I find this problematic, because it can lead to subtle bugs, when a few entries in a large vector become complex and thus completely change the ordering relations on it.

Let's see how other environments to it:
Octave, as we all know, uses abs-based order.
Matlab is inconsistent, it uses abs-based order for sort, max and min, but compares only the real part (that is, not even lexicographic order) when < or > is evaluated directly.
R, according to comment 15 on bug #52919, uses lexicographic order.

All the other environments I could think of that define complex numbers refrain from defining an order, including Fortran, C, C++ and Python. That's actually what I would do also, so that programming errors that lead to complex values where there should be none raise errors sooner, and if anybody wants to actually compare or sort complex values, to do it explicitly.

As to the comments: Michael Godfrey, both in this thread and in bug #52919 you seem to be much in favour of abs-based order, commenting on R using lexicographic order as "Looks like they have not given it much thought". Perhaps R inherited it just from S, as Octave inherited a host of decisions from Matlab, but I have to admit that I also seem to have given it not much thought as I fail to see why it should be obvious that lexicographic sorting can only be chosen due to lack of thought. Further, you postulate "For complex the ordering is a measure of distance in the complex plane" (here should be inserted "distance from zero", as the distance from any other point would also give a perfectly well-defined ordering relation). But this postulate implies already the solution: of course, when you want to order by the distance from zero, you do arg-based sorting. My point is that "the order of any two complex numbers is inherited from the order of the nearest real numbers" is an equally valid postulate. What we want to do here is to collect arguments for both possibilities. And how Knuth would sort complex values is beside the point, of course he would sort them as he orders them (I would actually expect him to discuss sorting algorithms only in terms of generic sets with total order). So we are back at having to deliberate which identities we want our order to fulfill.

Michael Leitner <mleitner>
Wed 31 Jan 2018 12:17:59 AM UTC, comment #3:

Sorry to say that Knuth vol. 3 seems not to deal
with sort of complex. Sigh...

more study is needed.

Michael Godfrey <godfrey>
Project Member
Tue 30 Jan 2018 04:39:47 PM UTC, comment #2:

Expanding on comment #1:

A complex value Z can be represented in several forms with the obvious ones being Cartesian (x + iy) or polar (Ae^{i theta}). When Matlab and Octave compare complex numbers they use the polar representation. Hence it is natural to first compare by magnitude (A) and only if necessary consider the phase angle theta.

This is different from comparing a real value which uses the Cartesian representation and only considers 'x'.

Rik <rik5>
Project Administrator
Tue 30 Jan 2018 11:52:51 AM UTC, comment #1:

This can be made into a long argument, but it should start
with:

For reals the ordering is along the real line.

For complex the ordering is a measure of distance in
the complex plane. That is why phase enters into the
complex sort. I think that there is more literature
on this which should be looked up.

Michael Godfrey <godfrey>
Project Member
Tue 30 Jan 2018 10:26:33 AM UTC, original submission:

I am splitting up bug #52919. Now to the most fundamental issue:

When Octave compares complex numbers, it first compares the absolute values and then the phase angle (proviso bug #53011). For sorting, the same comparison is used.

When Matlab compares complex numbers, it only considers the real part. For sorting, it does the same as Octave. Thus, Matlab is not consistent.

Octave wants to be consistent, and it wants to be compatible with Matlab. Obviously, this is impossible, there are two internally consistent choices and one compatible choice. As I will argue now, I would find the other consistent choice better than the current one.

Actually, there is another criterion where it would be nice to be consistent, which is how complex numbers with zero imaginary part are treated with respect to comparison. Indeed, there is the concept of promotion and narrowing (for the latter see bug #52919). Consider the following code:

a is created and the two negative elements are smaller than zero. When now any value inside a is made complex, the whole vector a is promoted to class complex, which changes the ordering relations, and no value is smaller than zero (because the absolute value is now compared). When you only consider a subset where every value has an imaginary part equal to zero, this vector is again narrowed to class real, and everything works as before, the same when you set the one complex value to real. I argue that this is also an issue of internal inconsistency, because the result of the comparison of some elements depends on the value of other elements (and when you have negative numbers, this really is an issue). As far as I understand, Matlab is consistent in this regard, as it only considers the real part, thus real numbers are a subset of complex numbers with consistent ordering in this regard. Another nice consequence of the Matlab-ordering is that it follows always from a<b that a+c<b+c, whatever a, b and c (real or complex -- for Octave only one of the three needs to be complex to potentially violate this law).

So Matlab's ordering (which could be complemented by an imag-based ordering to break ties on the real part and thus give a total order) has in my view more nice properties than the abs-based ordering. If Octave switched to it (both with respect to comparison as well as sorting), it would stay half-compatible, it would stay consistent with respect to ordering and comparison, and it would become more consistent (or at least intuitive, that is, less time taken for hunting programming errors) with respect to seeing real numbers as special case of complex numbers.

In fact, as I am not at all convinced that it is a good idea to blindly compare complex numbers at all, for me it is not so important how the ordering relations are defined on them. But what would help me was to introduce a warning when I compare complex numbers, because I cannot remember ever doing this intentionally. Rather, this would be a hint for a programming error on my part and would have already saved me a few hours bug-hunting. Thus, when it should be the consensus that it is a bad idea to change the ordering relations on complex numbers at a whim, please consider this as a feature request for such a warning (I see only unique as a valid use case for comparing complex numbers, so there it should probably suppressed, if this is possible).

Michael Leitner <mleitner>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by amro_octave
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by godfrey (Posted a comment)
  • -email is unavailable- added by mleitner (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

     

     

    Follows 1 latest change.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-02-02 amro_octave Carbon-Copy- => Added amro_octave

    Back to the top


    Powered by Savane 3.3