Comparison of complex numbers

[gulfaraz]

The following is the output when comparing complex numbers.

var a = math.complex("2 + 3i");
var b = math.complex("3 + 4i");
math.larger(a, b)
math.js:5309 Uncaught TypeError: No ordering relation is defined for complex numbers
    at Complex, Complex (math.js:5309)
    at Object.larger (eval at _typed (math.js:57838), <anonymous>:111:16)
    at <anonymous>:1:6

'No ordering relation is defined for complex numbers'

Which is mathematically accurate, but was of little use in implementing logistic regression.

A few searches later I found this comment --

It's indeed not possible to order complex numbers since they have no ordering defined. You can compare whether two complex numbers are equal or not, but not if one is larger than the other.

-- which made sense and confirmed that I would need to find a workaround in order to proceed with my calculations.

I took octave as the reference and implemented their partial ordering logic

For complex numbers, the following ordering is defined: z1 < z2 if and only if

abs (z1) < abs (z2)
|| (abs (z1) == abs (z2) && arg (z1) < arg (z2))

This is consistent with the ordering used by max, min and sort, but is not consistent with >MATLAB, which only compares the real parts.

I looked up MATLAB's implementation for complex comparison and they only compare the real parts of the numbers - which is different from octave's implementation mentioned above. Either implementation could or could not be the preferred partial ordering for the user but it's not a show stopper.

I feel the library should implement some sort of default partial ordering instead of an absolute error which halts the program. Either of the above implementations or a different partial ordering altogether so that the calculations don't completely halt.

I used the following code to work around the problem.

math.isComplex = function (value) {
    return value != null && value.isComplex;
};

math.complexLarger = function (a, b) {
    var isLarger = true;
    if(math.isComplex(a) || math.isComplex(b)) {
        isLarger = math.abs(a) > math.abs(b) || (math.abs(a) == math.abs(b) && math.arg(b) > math.arg(b));
    } else {
        isLarger = math.larger(a, b);
    }
    return isLarger;
};

Which resulted in

var a = math.complex("2 + 3i");
var b = math.complex("3 + 4i");
math.complexLarger(a, b); // returns false
math.complexLarger(b, a); // returns true

It would be nice to have a default solution out of the box. That's my 2 cents.

Also, thank you for the awesome library.

[josdejong]

Thanks Gulfaraz, yeah, so far we've simply don't do ordering of complex numbers. It could make sense to implement it. Not sure which of the two solutions is preferable.

Can you explain a little bit more about your use case, why you need this?

[gulfaraz]

I was porting the fmincg (conjugate gradient) function to javascript from the ml-class by Andrew Ng.

The function goes through a bunch of iterations where the numbers keep changing (yes, this is my existing knowledge on machine learning or numerical calculations - have a lot to learn).

During these iterations some of the matrices start to hold complex numbers and along comes a condition of d2 > -SIG*d1 where the d2 part had become a complex number in a sqrt operation earlier in the loop. And the iteration failed.

I had used math.larger for that comparison there - a few minutes of debugging led me to the solution I shared above.

If I was porting the code from MATLAB - I would've implemented the MATLAB implementation. It wasn't a calculated preference but merely a "try to replicate as much as possible" decision making.

Apparently, MATLAB is used much more extensively when compared to octave. It would be wise to find out what python libraries do - a bit of googling showed me there is at least one user trying to solve the problem.

Reasoning to compare with python -> While moving to programming from MATLAB and Octave - python is the language of choice. Should also checkout R which was also mentioned in the course.

TL;DR - I do not think the choice of implementation matters as long as the calculations don't break.

[josdejong]

Thanks for the extra explanation. Ok then let's implement ordering for complex numbers.

I still need a bit more time to consider what would be the most appropriate way of ordering: by real value or by absolute value. Any extra arguments for one or the other are welcome.

[gulfaraz]

I made a PR assuming the real value based on this stackoverflow post

I chose the MATLAB's approach was for its popularity over Octave and also because it's easier to change the code to take real parts a.re > b.re than do 5 operations. (math.abs(a) > math.abs(b) || (math.abs(a) == math.abs(b) && math.arg(b) > math.arg(b)))

Please review the changes and if I've missed some dependency.

[josdejong]

That's odd... Three days ago when I reviewed your PR I also entered a reply here about the choice for the way of ordering, but apparently I didn't press the "Comment" button or something.

I'm not really convinced that ordering by real value is the best solution. To me, comparing the absolute value sounds way more logical. The stackoverflow article you link to gives performance as argument. That can be a good reason. There are also issues though with this choice of Matlab (see this discussion): < and > compares the real parts of complex numbers, but min and max compare the absolute value. That is quite inconsistent.

In this case I find consistency and logical behavior more important than staying compatible with Matlab (and apparently Octave thought the same - though they weigh Matlab compatibility much higher that mathjs does). What do you think?

[gulfaraz]

I'm not sure if there is a best solution here. I believe the application use case defines the ordering relation and others may want to stick to a specific ordering relation. So logical behavior is a matter of opinion.

Although, consistency should be prioritized higher than being compatible with any other software. If mathjs should assume the absolute value for ordering complex numbers - let us stick to that consistently. I do not think we should compromise on consistency.

On searching for articles on absolute value of complex numbers, gives results like this one and this one. Highlighting the exact lack of ordering we are trying to bypass. Which brings us back full circle.

I am fine with sticking to the absolute values unless anyone can think of a scenario where calculations/comparisons might break as a result of this assumption.

[balagge]

I just noticed this issue, sorry for a late comment.

To me ordering of complex numbers is very strange, it has no mathematical basis and if implemented, it would be nice to have an option to turn it off.

[ericman314]

Here are my two cents.

Ordering by absolute value will lead to these unexpected results:

-5 > -3                 false
-5 + 0i > -3 + 0i       true

5i > 3i            true
-5i > -3i          true

[ericman314]

If we order by real part, then a user could apply a transform to each side of the inequality to achieve any behavior:

a > b              Compare real parts
a * -i > b * -i    Compare imaginary parts
abs(a) > abs(b)    Compare absolute value

But I'm not sure that will work with functions like max and min, which would return the transformed value instead of the original value.

[josdejong]

@ericman314 nice examples of counter-intuitive results. I'm afraid that any option we choose has "unexpected results", but maybe comparing by real part isn't that bad after all. At least the behavior should be consistend for the relational operators < and > and functions like min and max.

Comparing complex numbers is indeed weird. If I understand it correctly the reason is not to see which of two complex numbers is largest, but to be able to order a list of complex numbers in "some" deterministic way. I'm still looking for more use cases. Maybe in set theory or something?

@gulfaraz wouldn't your initial issue of d2 > -SIG*d1 breaking because one of the variables became complex output of sqrt be solved by configuring math.config({predictable: true})?

From a practical point of view: it is currently already possible to implement the comparison of your choice yourself, like:

abs(a) > abs(b)
re(a) > re(b)
im(a) > im(b)
# ... other creative solutions

It's also possible to override the built-in error that you get right now when comparing complex numbers:

// override default implementation of comparing complex numbers (which throws an error)
math.import ({
  smaller:   math.typed({ 'Complex,Complex': function (a, b) { return a.re <  b.re } }),
  smallerEq: math.typed({ 'Complex,Complex': function (a, b) { return a.re <= b.re } }),
  larger:    math.typed({ 'Complex,Complex': function (a, b) { return a.re >  b.re } }),
  largerEq:  math.typed({ 'Complex,Complex': function (a, b) { return a.re >= b.re } })
}, { override: true });

// then:
math.eval('2+3i < 3+1i') // returns true

[gulfaraz]

math.config({predictable: true}) prevents the calculations from breaking. This is good enough for my use case. Also, if I really want a specific ordering relation then the override mechanism will be the perfect approach.

From A New Approach To Ordering Complex Numbers published in 2008, the suggested approach is summarized in 6.7

6.7. Well-Ordering Property: If C be a non-empty set of complex numbers, then C has a least complex number(z) such that z≤w for every w in C in the sense that either │z│<│w│ or [z]=[w].

The paper also lists the alternatives ordering relations in 2.9 - 2.12. Of which we currently know that MATLAB and Octave use the Pseudo-Ordering of Complex Numbers options.

And this link which concludes with it is impossible to (sensibly) order complex numbers.

At this point, I want to refer to the first post on this issue where the sensibility of the ordering isn't the priority. But the exception in the calculations because maths itself has no mathematical rule (similar to the case of "divide by zero" but we do not throw an exception here either).

We could choose to

1. Ignore ordering completely until there is an exact definition (IF it can ever be defined) and throw when this condition is encountered.

The user can override these implementations using the approaches described in the above comment. This is adequate control to override any mathematical rules the project assumes.

2. Implement some sort of partial ordering which has no mathematical basis but for some unknown reason is used in MATLAB/Octave.

As there is no solid evidence for implementing any kind of ordering, any benefit by doing this heavily relies on the consumer of the mathjs library. If the user base is not similar to MATLAB/Octave then I do not recommend this option. But if there are more users who are trying to use mathjs to write programs that require MATLAB/Octave calculations than those who depend on mathematical strictness this option seems to be the way to go.

Is there another alternative ?

[josdejong]

Thanks for doing this research @gulfaraz.

Since the original issue has been solved with math.config({predictable: true}), I lack concrete use cases where we need ordering of complex numbers. As long as we don't have a concreet need for it, it may be best not to implement ordering for complex numbers. If people really need it they can use one of the available workarounds, and we can continue this discussion. Does that make sense?

[gulfaraz]

Works for me 👍

[josdejong]

👍

[josdejong]

Ok then... Time to reopen this issue already :D

Ordering of complex numbers is indeed needed for set operations. We could do without but that will lead to inefficient code, See #858.

We figured that both sorting by real part or absolute value will not work though: this will not uniquely sort differing values like 1+i and 1-i. @Nekomajin42 came with a smart idea though: first sort by the real part, and if two has the same real part, then sort them again by the imaginary part.

I think that's a really interesting and simple idea, which gives uniquely ordered values which are probably way easier to reason about for a human being too.

[gulfaraz]

@josdejong should I reopen the PR and implement this approach ?

[josdejong]

Thanks @gulfaraz, yes that would be great! Thanks

[balagge]

Is it absolutely necessary to change the default comparison functions for this very specific use case?
And changing the behavior of comparison operators < > as well, contrary to mathematical definition?
maths is a mathematical environment, implementing unorthodox behavior seems undesireable to me.
For the specific use case, a separate, dedicated (maybe even local) function could be used, I guess.

[josdejong]

That's a good point. From a pragmatic point of view it's nice to have this "just" working, but indeed there is no mathematical meaning for this. So then the question then is: will it do harm? Does it do harm in for example Matlab and Octave which each have their own implementation? I tend to think that it does do little harm whilst it's very convenient to have when you need it (and very unpractical if it isn't there).

I don't think "special internal behavior" would be the right solution either: if we need it now internally, you can be sure that someone will need it externally as well. An other option that you suggested before is to make this behavior configurable. We could do that though I'm careful with introducing more configuration as that complicates the library.

Anyone else any thoughts on this?

[josdejong]

Just thinking aloud: maybe we could only do sorting of complex numbers in the sort function, and not support it in min, max, smaller, smallerEq, larger, largerEq.

[balagge]

'Does it do harm?'
In the sense that it gives false positive results, yes, it does.
For the comparison a <b I expect a runtime error, if any of those values are not real numbers.
If it gives 'true' or 'false' instead, then the code will break later, not exposing the actual point where the problem really occured.
Of course, I assume some source that is written with mathematical intuition in mind.

'Matlab and Octave'? There is a lot of legacy in such environments. I do not know why those people chose to implement such nonsense, but blindly copying suspicious behavior seems foolish to me.

Sorry for the wording, I am quite passionate about this one... :)

[Nekomajin42]

@josdejong
I think it's a good compromise.

[josdejong]

Thanks for the feedback. Appreciate your concerns Paál. We've made decisions to go a different route than Matlab before and indeed try to make a good choice and not blindly follow the big guys. This is a great discussion :).

There is no mathematical definition for comparing complex numbers. We also don't have concrete use cases except sorting a list in a deterministic order (for the new set functions). It's easy to add features but hard to remove them later on, so from that point of view it's safer to wait until there are actual use cases. So, if everybody agrees, I think it's ultimately better to remove the complex number implementations for smaller, smallerEq, larger, largerEq, and compare. (Sorry @gulfaraz, that will mean we have to remove most of your work again. It played an important role in getting a clear vision in this discussion though)

We do need a solution though to be able to sort a list with values including complex numbers for the set functions. We could implement support for ordering complex numbers in the sort function. That still feels a a bit inconsistent, as it still suggests the first value is the smallest and the last one the largest. Maybe we can introduce a new function to make the meaning more clear, something like orderDeterministically, or setOrdered or setSort (similar naming as the set functions).

[firepick1]

The problem we're trying to solve is deterministic iteration. Sets are unordered. But we may want a reproduce-able way to iterate over a set. This maps directly to the problem of ordering tuples--there are multiple orderings. Consider the natural ordering of comparing tuples element by element. Since complex numbers are (real, imaginary) this would be:
int cmp = (a.real - b.real) || (a.imag - b.imag);
This "natural ordering" extends to arbitrary dimensions and can be expressed "sort left-to-right, ascending". It's also how most people would order a data table, hence, "natural ordering"

[Nekomajin42]

@josdejong
A setSort method is definitely an interesting idea.

The set functions support string arrays. However, if I have a set which contains strings and other types, the functions fail, because sorting between numbers and strings are not supported.

Now, I know it's a math library, but sets can contain strings, in my opinion. With a setSort method, we could easily solve both problems, and also provide a functions for manual lexicographical ordering of mixed arrays.

This way we don't do any harm to complex numbers, but we can solve my problem and also provide an additional feature to the library, which can be useful in some cases. What do you guys think?

[firepick1]

At the risk of going full circle, a comparator is more general. And a comparator can order arrays or heaps or whatever. Since a comparator is an object, it can take options (e.g., ignore case, convertStringToNumber, etc.). With a comparator we can sort everything, not only sets.
And a comparator has a compare(a,b) method that returns an integer.

[josdejong]

@firepick1 very well said. This natural ordering is indeed what we're looking for (and the current implementation in the develop branch by @gulfaraz does use the exact implementation you propose (including compare function).

You're indeed going full circle by suggesting to solve this with a comparator. Ideally:

• We do want to be able to deterministically sort a list containing "anything".
• But we don't want to compare complex numbers with functions like compare, larger, smaller since that's mathematically undefined behavior

Creating a clearly separate function for this ordering makes most sense to me so far.

The naming of this new function is very important, users must understand that it's not sorting in ascending, mathematical order. I like the "natural" naming that Karl proposes. We could introduce this setSort function, but maybe even nicer, add a new mode to the existing sort function, like:

sort([...], 'asc')
sort([...], 'desc')
sort([...], 'natural')  // Sorts complex numbers and other tuples
                        // Sorts objects
                        // Sorts mixed types
                        // Sorts strings in a natural way, i.e. ['1', '2', '10'] 
                        //     instead of ['1', '10', '2']

What I like about this solution is that it does not introduce a new function, and it makes very clear that it's sorting behavior is not mathematical ascending order.

[Nekomajin42]

@josdejong
I like this natural parameter idea.

Can it work with mixed data types? For example, a set can contain numbers and complexs, or numbers and letters.

[josdejong]

Well it's up to us to define the exact behavior of the natural sorting, but I think in general it should accept a list containing any type of data including mixed data types.

It could for example first order by type (string, number, complex, unit, ...), and then for each type order the items in a natural way. We can start simple by adding support for complex numbers, and changing the ordering of strings to natural sorting. Later on we can also add support for ordering objects and maybe also nested arrays.

[firepick1]

Sorters and comparators are different. Separation of concerns allows sorters to focus on algortihms (e.g., heapsort, binarysort, etc.) and comparators to focus on comparison:

var cmp = new mathjs.Comparator({tuples: "natural"});
var list = [1, mathjs.complex({re:2,im:2})];
var sortedList = list.sort((a,b) => cmp.compare(a,b));
var sortedSet = new Set();
sortedList.forEach(e => sortedSet.add(e))

Since JS defines Set as iterable following insertion order, the above creates an ordered set as defined by the ordering of the customizable cmp comparator.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

[josdejong]

Yes that's true.

The current math.sort uses math.compare, and I think if we go the route discussed above, we will create a new comparator math.compareNatural, and create a new shortcut for it in the sort function, like math.sort([...], 'natural') which then calls math.sort([...], math.compareNatural).

[firepick1]

math.compareNatural would also allow us to merge infinite streams, which are not sortable in our lifetime

[josdejong]

I've made a start with implementing compareNatural. I've reverted support for complex numbers in the relational functions, and changed the set functions to use natural sorting.

The function is a WIP, and needs to be worked out further:

• How to compare matrices/arrays? Elementwise like compare? Or start comparing values of the two matrices until one of the two is smaller/larger and then return -1,0, or 1?
• Currently the values aren't ordered by type, so sorting [1, math.bignumber(1)] is not deterministic.

[firepick1]

Oddly, this issue crisscrosses with the null issue. Consider:
compareNatural([1,2], [1,2,3])
Given the definition of null, one might then take the above to be equivalent to:
compareNatural([1,2,null], [1,2,3])
Here the situation gets tricky because our decision may hinge on what compareNatural(null, 3) should return.
Option1) null. This is the strict consistent interpretation
Option2) 1. This may actually be the "natural" as in "a convenient and broadly acceptable default"
Now with matrices, the situation becomes quite tricky given that there are two natural orders for comparing by element: row major, column major. Perhaps just throw an exception and let that decision bake in a discussion thread. I honestly couldn't say which is more natural (just look at left-right and right-left and up-down natural languages!)

[josdejong]

I think the compareNatural function should always do something and should not throw errors for any types. It's not mathematically defined ordering but should give a deterministic ordering that feels "logic" to humans.

How about:

• First compare by type , where numeric types are considered the same "group". That solves comparing null with numbers and comparing complex numbers against units.
• Then, apply sorting depending on the type.
  • numbers by their value. Compare numbers and BigNumbers and Fractions
  • complex numbers first by real value, and if equal, compare their imaginary part
  • units first by unit, then by normalized value
  • strings by their natural value
  • null is just null
  • booleans first false then true
  • objects by their number of properties, if equal, compare the values of the objects properties after ordering the properties naturally.
  • arrays first by their number of dimensions, then by the size of each dimension, and if equal in size, compare value by value until there is a value that's not equal.

[josdejong]

hm, I just realize that we can't put numeric types in the same group, and that in order to give deterministic results, the comparator should not consider 1 and bignumber(1) equal. That's not "natural" behavior though.

So I think we have to fine another name for this comparator comparing anything, name it compareAnything or compareApplesAndPears. And separately, we have to adjust the behavior of the existing math.compare for strings to comparing their numeric value (i.e. do mathematical comparison) as discussed in #680, which will be a breaking change.

[josdejong]

Thinking about it, we can generalize this comparator even more. What the set functions need is just "any" sorting as long as it is strict and deterministic. It basically boils down to needing a deep strict comparator. Similar to for example deep-strict-equal but then returning a comparison result -1, 0 or 1 instead of true/false.

[harrysarson]

Re numeric types, one could compare first based on the numerical value and second on the type. E.g.

• 1 < bignumber(2)
• bignumber(1) < 2
• 1 < bignumber(1) // comparison based on type
  This would be deterministic but also (to me at least) feels natural.

[josdejong]

That's, a smart idea Harry, thanks

[josdejong]

I've experimented with a sort of deep-strict-equal function but this is quite tricky. Such a function only recons with properties on plain objects, and doesn't understand what it's comparing. That can lead to unexpected behavior. The ordered outcome is also quite often counter intuitive, and I think that it's important to have a function that orders items in a logical way.

So I will continue working out the compareNatural function.

[josdejong]

I've now fully implemented compareNatural, see unit tests in the develop branch to get an idea of the behavior: https://github.com/josdejong/mathjs/blob/develop/test/function/relational/compareNatural.test.js

hope to do a release today. (finally...)

[josdejong]

compareNatural is now available in v3.14.1

[Nekomajin42]

So I should update the set functions?

[josdejong]

@Nekomajin42 I already updated the set functions to use compareNatural :)