comparison of CDF (or any inexact) elements needs fixing

[craigcitro]

So currently, we compare elements of inexact rings like CDF by just comparing their components as doubles. We use this for sorting, and expect the results to be consistent between runs, architectures, etc. However, this is wildly untrue. Here's a good example:

sage: z1, z2 = [ x[0] for x in f.roots()[-2:] ]
sage: R = CDF['x']
sage: f = R([17,1,0,0,0,1]) ; f
1.0*x^5 + 1.0*x + 17.0
sage: f.roots()
[(-1.72502775061, 1),
 (1.4372759883 + 1.06991737978*I, 1),
 (1.4372759883 - 1.06991737978*I, 1),
 (-0.574762112991 + 1.65506825348*I, 1),
 (-0.574762112991 - 1.65506825348*I, 1)]
sage: z1, z2 = [ x[0] for x in f.roots()[-2:] ]
sage: z1
-0.574762112991 + 1.65506825348*I
sage: z2
-0.574762112991 - 1.65506825348*I
sage: z1.real() == z2.real()
False

Notice that the +/- ordering is different for the two pairs of complex conjugate roots. What we should do is pass a parameter to __cmp__ that describes a threshold such that if the difference is smaller than this threshold in absolute value, things compare equal. This could even be a parameter to the ring.

There are a ton of questions this brings up, such as, "how is this done in other systems?" Notice this also underlies the following confusing result:

sage: [ f(x[0]).is_zero() for x in f.roots() ]
[False, False, False, False, False]

Someone should do some research and start a sage-devel conversation, probably.

Component: numerical

Issue created by migration from https://trac.sagemath.org/ticket/4544

[craigcitro]

comment:1

Note: this was also part of the problem underlying #4469. In particular, two things need to happen to fix #4469 properly:

• in sage/rings/polynomial/polynomial_element.pyx, the roots function should also call crts.sort().

• someone should fix this bug, so that we actually have something resembling dictionary order on CDF, as claimed in the _cmp_ method for CDF elements.

[aghitza]

comment:2

changed the title so it doesn't get picked up by the wrong trac report

[sagetrac-cwitty]

comment:3

Attachment: trac4544.patch.gz

I'm totally unwilling to add some sort of epsilon for complex comparison in general; it's just a bad idea.

However, the goal of sorting the output of .roots() is not so bad, and I'm willing to put an epsilon comparison in that sorting routine (since it's basically only for display, and especially since it helps doctest consistency); so that's what I've done in the attached patch.

[sagetrac-mabshoff]

comment:4

Carl Witty claims that this ticket will fix #5167, so let's make this a blocker for 3.3.

Cheers,

Michael