Sage: Ticket #11309: Sage sees - x + y > 0, - y + x >= 0, and x - y > 0 as equivalent
https://trac.sagemath.org/ticket/11309
<p>
-x + y > 0 and x - y > 0 are treated the same in Sage.
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> version<span class="p">()</span>
<span class="s">'Sage Version 4.6.2, Release Date: 2011-02-25'</span>
sage<span class="p">:</span> <span class="p">(</span><span class="o">-</span>x <span class="o">+</span>y <span class="o"><</span> <span class="mi">0</span><span class="p">)</span> <span class="ow">in</span> <span class="p">[</span>x <span class="o">-</span>y <span class="o"><</span> <span class="mi">0</span><span class="p">]</span>
<span class="bp">True</span>
Set<span class="p">([</span><span class="o">-</span>x <span class="o">+</span>y <span class="o">>=</span> <span class="mi">0</span><span class="p">,</span>x <span class="o">-</span>y <span class="o">>=</span> <span class="mi">0</span><span class="p">])</span>
<span class="p">{</span><span class="o">-</span>x <span class="o">+</span> y <span class="o">>=</span> <span class="mi">0</span><span class="p">}</span>
</pre></div></div><p>
and they have the same Hash
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> var<span class="p">(</span><span class="s">'x,y'</span><span class="p">)</span>
<span class="p">(</span>x<span class="p">,</span> y<span class="p">)</span>
sage<span class="p">:</span> <span class="nb">hash</span><span class="p">(</span><span class="o">-</span>x <span class="o">+</span> y <span class="o">></span> <span class="mi">0</span> <span class="p">)</span>
<span class="mi">1221566266</span>
sage<span class="p">:</span> <span class="nb">hash</span><span class="p">(</span><span class="o">-</span>x <span class="o">+</span> y <span class="o">>=</span> <span class="mi">0</span> <span class="p">)</span>
<span class="mi">1221566266</span>
sage<span class="p">:</span> <span class="nb">hash</span><span class="p">(</span>x <span class="o">-</span> y <span class="o">>=</span> <span class="mi">0</span> <span class="p">)</span>
<span class="mi">1221566266</span>
sage<span class="p">:</span> <span class="nb">hash</span><span class="p">(</span><span class="o">-</span>y <span class="o">+</span> x <span class="o">>=</span> <span class="mi">0</span> <span class="p">)</span>
<span class="mi">1221566266</span>
sage<span class="p">:</span> <span class="nb">hash</span><span class="p">(</span>x <span class="o">-</span> y <span class="o">></span> <span class="mi">0</span> <span class="p">)</span>
<span class="mi">1221566266</span>
</pre></div></div><p>
It seems to me that Sage treats <code>></code>, <code>>=</code>, and <code>==</code> the same (see <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/7660" title="defect: arithmetic with equations and inequalities confusing (needs_work)">#7660</a>). If this is true then it's a serious problem and needs to be addressed.
</p>
<p>
Apply:
</p>
<ol><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11309/trac_11309-fix-comparison-of-comparisons.patch" title="Attachment 'trac_11309-fix-comparison-of-comparisons.patch' in Ticket #11309">trac_11309-fix-comparison-of-comparisons.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11309/trac_11309-fix-comparison-of-comparisons.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11309/trac_11309-equate-flipped-comparisons.patch" title="Attachment 'trac_11309-equate-flipped-comparisons.patch' in Ticket #11309">trac_11309-equate-flipped-comparisons.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11309/trac_11309-equate-flipped-comparisons.patch" title="Download"></a>
</li></ol>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11309
Trac 1.1.6tnvFri, 06 May 2011 22:53:19 GMTdescription changed
https://trac.sagemath.org/ticket/11309#comment:1
https://trac.sagemath.org/ticket/11309#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11309?action=diff&version=1">diff</a>)
</li>
</ul>
TicketkiniSat, 07 May 2011 00:42:12 GMTcc set
https://trac.sagemath.org/ticket/11309#comment:2
https://trac.sagemath.org/ticket/11309#comment:2
<ul>
<li><strong>cc</strong>
<em>kini</em> added
</li>
</ul>
TicketkiniWed, 15 Jun 2011 23:22:30 GMTdescription changed
https://trac.sagemath.org/ticket/11309#comment:3
https://trac.sagemath.org/ticket/11309#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11309?action=diff&version=3">diff</a>)
</li>
</ul>
TicketkiniThu, 16 Jun 2011 00:34:56 GMTstatus changed; author set
https://trac.sagemath.org/ticket/11309#comment:4
https://trac.sagemath.org/ticket/11309#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Keshav Kini, Burcin Erocal</em>
</li>
</ul>
<p>
Ready for review! Thanks to Burcin for walking me through the Cython code.
</p>
TickettnvThu, 16 Jun 2011 04:24:50 GMT
https://trac.sagemath.org/ticket/11309#comment:5
https://trac.sagemath.org/ticket/11309#comment:5
<p>
Thanks for creating the patch!!
</p>
<p>
I don't know how to apply this patch though - if you can walk me through it then I can test.
</p>
<p>
But in the mean time, what are the result for these commands ? If the results are different than the defected version above and as expected then probably the patch is correct.
</p>
<p>
sage: (-x +y < 0) in [x -y < 0]
</p>
<p>
Set([-x +y >= 0,x -y >= 0])
</p>
<p>
sage: var('x,y')
(x, y)
sage: hash(-x + y > 0 )
sage: hash(-x + y >= 0 )
sage: hash(x - y >= 0 )
sage: hash(-y + x >= 0 )
sage: hash(x - y > 0 )
</p>
TicketkiniThu, 16 Jun 2011 04:37:58 GMT
https://trac.sagemath.org/ticket/11309#comment:6
https://trac.sagemath.org/ticket/11309#comment:6
<p>
I've changed the patch a little bit just now, by the way.
</p>
<p>
To apply the patch, go to <code>devel/sage/</code> inside your sage directory, and type <code>sage -hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/11309/trac_11309-fix-comparison-of-comparisons.patch</code>, type <code>sage -hg qpush</code>, type <code>sage -b</code>, and finally launch sage to test the patch!
</p>
<p>
Your examples are fixed, yes. You can see them listed inside the patch, where I added some more examples in the documentation of the function I changed.
</p>
TicketkiniThu, 16 Jun 2011 04:47:42 GMT
https://trac.sagemath.org/ticket/11309#comment:7
https://trac.sagemath.org/ticket/11309#comment:7
<p>
Oh, by the way, I didn't fix the hashes. They're screwed up anyway, so this solution avoids using them to decide anything about whether expressions are the same or not. We might fix that in a later ticket...
</p>
TickettnvThu, 16 Jun 2011 05:04:15 GMT
https://trac.sagemath.org/ticket/11309#comment:8
https://trac.sagemath.org/ticket/11309#comment:8
<p>
Thanks for the info.
</p>
<p>
Which Sage version do I apply the patch to ? the latest 4.7 ? I'll do that tomorrow at work
</p>
<p>
if they still give the same hashes then (-x +y < 0) in [x -y < 0] still gives True and
Set([-x +y >= 0,x -y >= 0]) still eliminates one of them . Correct ?
</p>
TicketkiniThu, 16 Jun 2011 05:19:55 GMT
https://trac.sagemath.org/ticket/11309#comment:9
https://trac.sagemath.org/ticket/11309#comment:9
<p>
No, incorrect, because I changed the code to not use the hashes at all when doing the comparison. The hashes are now irrelevant to this operation. However kcrisman found a bug in my patch so I will update it again in just a second...
</p>
TicketkiniThu, 16 Jun 2011 05:48:41 GMTstatus changed
https://trac.sagemath.org/ticket/11309#comment:10
https://trac.sagemath.org/ticket/11309#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
OK, this looks like it's going to take a little while, I'm getting some unexpected doctest errors... I'll fix it in the morning :)
</p>
TicketkiniThu, 16 Jun 2011 06:07:00 GMTstatus changed
https://trac.sagemath.org/ticket/11309#comment:11
https://trac.sagemath.org/ticket/11309#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Never mind, ready for review again!
</p>
TicketkiniThu, 16 Jun 2011 06:16:34 GMTcc changed; owner deleted
https://trac.sagemath.org/ticket/11309#comment:12
https://trac.sagemath.org/ticket/11309#comment:12
<ul>
<li><strong>owner</strong>
changed from <em>burcin</em> to <em>(none)</em>
</li>
<li><strong>cc</strong>
<em>kcrisman</em> added
</li>
</ul>
TicketkiniThu, 16 Jun 2011 06:17:02 GMTowner set
https://trac.sagemath.org/ticket/11309#comment:13
https://trac.sagemath.org/ticket/11309#comment:13
<ul>
<li><strong>owner</strong>
changed from <em>(none)</em> to <em>burcin</em>
</li>
</ul>
<p>
burcin got deleted from this ticket... that trac bug is annoying!
</p>
TicketkcrismanThu, 16 Jun 2011 06:22:30 GMT
https://trac.sagemath.org/ticket/11309#comment:14
https://trac.sagemath.org/ticket/11309#comment:14
<p>
Code is correct (corner cases discussed in person, so that e.g. <code>(x < y) != x </code> is True.
</p>
<p>
<code>GEx e</code> seems far from where it comes from.
</p>
TicketkiniThu, 16 Jun 2011 06:26:56 GMTattachment set
https://trac.sagemath.org/ticket/11309
https://trac.sagemath.org/ticket/11309
<ul>
<li><strong>attachment</strong>
set to <em>trac_11309-fix-comparison-of-comparisons.patch</em>
</li>
</ul>
TicketkiniThu, 16 Jun 2011 06:27:31 GMT
https://trac.sagemath.org/ticket/11309#comment:15
https://trac.sagemath.org/ticket/11309#comment:15
<p>
fixed! (sorry, that was left over from when I was doing something that made cython not like that declaration where it was)
</p>
TicketkiniThu, 16 Jun 2011 06:29:37 GMTkeywords changed
https://trac.sagemath.org/ticket/11309#comment:16
https://trac.sagemath.org/ticket/11309#comment:16
<ul>
<li><strong>keywords</strong>
<em>relational</em> <em>sd31</em> <em>__richcmp__</em> added
</li>
</ul>
TicketkcrismanThu, 16 Jun 2011 06:37:50 GMT
https://trac.sagemath.org/ticket/11309#comment:17
https://trac.sagemath.org/ticket/11309#comment:17
<p>
This looks good. Passing relevant tests.
</p>
TicketkcrismanThu, 16 Jun 2011 06:37:58 GMTstatus changed
https://trac.sagemath.org/ticket/11309#comment:18
https://trac.sagemath.org/ticket/11309#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketjdemeyerThu, 16 Jun 2011 11:56:37 GMTreviewer set
https://trac.sagemath.org/ticket/11309#comment:19
https://trac.sagemath.org/ticket/11309#comment:19
<ul>
<li><strong>reviewer</strong>
set to <em>Karl-Dieter Crisman</em>
</li>
</ul>
TickettnvThu, 16 Jun 2011 22:59:40 GMT
https://trac.sagemath.org/ticket/11309#comment:20
https://trac.sagemath.org/ticket/11309#comment:20
<p>
It now can tell that -x +y >0 is different than -y + x >= 0 but it says that -x+y >0 is not the same as y > x ---
</p>
<p>
or may be this is another problem ?
</p>
<pre class="wiki">sage: ( -x+y >0 ) == (y > x )
False
sage: (-x + y < 0) == (-x < -y)
False
sage: (x + y == 0) == (x == -y)
False
sage: (x - y == 0) == (x == y)
False
sage: (- x + y == 0) == (0 == -x + y)
False
sage: (x < y) == (y > x)
False
sage: (x == y) == (-x == -y)
False
sage: (x + y < 1 ) == (x + y -1 < 0)
False
</pre>
TickettnvThu, 16 Jun 2011 23:03:36 GMTstatus changed
https://trac.sagemath.org/ticket/11309#comment:21
https://trac.sagemath.org/ticket/11309#comment:21
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
This patch *breaks* the following
</p>
<p>
{{
Sage 4.7 (prepatched)
</p>
<p>
sage: (- x + y == 0) == (0 == -x + y)
True
sage: (-x + y == 0) == (0 == -x + y)
True
sage: (x < y) == (y > x)
True
</p>
<p>
Sage 4.7 (postpatched)
</p>
<p>
sage: (- x + y == 0) == (0 == -x + y)
False
sage: (-x + y == 0) == (0 == -x + y)
False
sage: (x < y) == (y > x)
False
</p>
<p>
}}}
</p>
TicketkcrismanThu, 16 Jun 2011 23:06:10 GMT
https://trac.sagemath.org/ticket/11309#comment:22
https://trac.sagemath.org/ticket/11309#comment:22
<pre class="wiki">Sage 4.7 (prepatched)
sage: (- x + y == 0) == (0 == -x + y) True sage: (-x + y == 0) == (0 == -x + y) True sage: (x < y) == (y > x) True
Sage 4.7 (postpatched)
sage: (- x + y == 0) == (0 == -x + y) False sage: (-x + y == 0) == (0 == -x + y) False sage: (x < y) == (y > x) False
</pre>
TicketkcrismanThu, 16 Jun 2011 23:06:48 GMT
https://trac.sagemath.org/ticket/11309#comment:23
https://trac.sagemath.org/ticket/11309#comment:23
<p>
{{ Sage 4.7 (prepatched)
</p>
<p>
sage: (- x + y == 0) == (0 == -x + y)
True
sage: (-x + y == 0) == (0 == -x + y)
True
sage: (x < y) == (y > x)
True
</p>
<p>
Sage 4.7 (postpatched)
</p>
<p>
sage: (- x + y == 0) == (0 == -x + y)
False
sage: (-x + y == 0) == (0 == -x + y)
False
sage: (x < y) == (y > x)
False
</p>
<p>
}}}
</p>
TicketkcrismanThu, 16 Jun 2011 23:07:52 GMT
https://trac.sagemath.org/ticket/11309#comment:24
https://trac.sagemath.org/ticket/11309#comment:24
<p>
Finally used preview...
</p>
<pre class="wiki">Sage 4.7 (prepatched)
sage: (- x + y == 0) == (0 == -x + y)
True
sage: (-x + y == 0) == (0 == -x + y)
True
sage: (x < y) == (y > x)
True
Sage 4.7 (postpatched)
sage: (- x + y == 0) == (0 == -x + y)
False
sage: (-x + y == 0) == (0 == -x + y)
False
sage: (x < y) == (y > x)
False
</pre>
TicketkcrismanThu, 16 Jun 2011 23:11:52 GMT
https://trac.sagemath.org/ticket/11309#comment:25
https://trac.sagemath.org/ticket/11309#comment:25
<pre class="wiki">-x+y >0 is not the same as y > x
</pre><p>
Correct. We use the philosophy (used elsewhere) that a comparison is True if you can prove it is True, and that otherwise it is False. False means that we can't prove it's True, and in general these kinds of simplifications are super hard. So all your examples need to be False, sadly.
</p>
<p>
As for the thing that breaks... I agree that is a problem. Great catch! Can you put your (real) name as a reviewer? (You should also feel free to add yourself to the <a class="ext-link" href="http://trac.sagemath.org/sage_trac/"><span class="icon"></span>main Trac page</a> as a developer/contributor.
</p>
TickettnvFri, 17 Jun 2011 03:47:41 GMTcc, reviewer changed
https://trac.sagemath.org/ticket/11309#comment:26
https://trac.sagemath.org/ticket/11309#comment:26
<ul>
<li><strong>cc</strong>
<em>tnv</em> added
</li>
<li><strong>reviewer</strong>
changed from <em>Karl-Dieter Crisman</em> to <em>Karl-Dieter Crisman, ThanhVu Nguyen</em>
</li>
</ul>
<p>
just put my name as reviewer -- thanks.
</p>
<p>
From your msg, would it be reasonable to add a SMT theorem prover package to Sage ? So that it can show equivalence of expressions (at least under some specific theories).
</p>
TicketkcrismanFri, 17 Jun 2011 03:50:07 GMT
https://trac.sagemath.org/ticket/11309#comment:27
https://trac.sagemath.org/ticket/11309#comment:27
<p>
There are some tickets open for things like this, I think, or something related, but I don't really know. Keshav or Burcin may know more.
</p>
TicketkiniSat, 18 Jun 2011 00:52:37 GMT
https://trac.sagemath.org/ticket/11309#comment:28
https://trac.sagemath.org/ticket/11309#comment:28
<p>
Hm. In order to eventually solve <a class="closed ticket" href="https://trac.sagemath.org/ticket/2778" title="enhancement: SymbolicFormula class (closed: duplicate)">#2778</a> and other such things, I think we need to allow nested relations after all. I talked to Burcin on IRC and he agrees. So we would plan to have all of these return an output which is the same as the input. If you wanted to force it to resolve, you could run bool() on them, and you would always get false, except when comparing <code>x < y</code> and <code>y > x</code>, <code>x <= y</code> and <code>y >= x</code>, <code>x == y</code> and <code>y == x</code>, and <code>x != y</code> and <code>y != x</code>, for symbolic expressions <code>x</code> and <code>y</code> (on kcrisman's insistence :) ). I'll need to implement this and figure out how it influences existing doctests (probably severely), so I'm leaving this as "needs_work" for now...
</p>
TicketkiniSat, 18 Jun 2011 00:53:07 GMT
https://trac.sagemath.org/ticket/11309#comment:29
https://trac.sagemath.org/ticket/11309#comment:29
<p>
Sorry, I meant <a class="new ticket" href="https://trac.sagemath.org/ticket/2744" title="enhancement: make symbolicequations deal with logical combinations (new)">#2744</a>, not <a class="closed ticket" href="https://trac.sagemath.org/ticket/2778" title="enhancement: SymbolicFormula class (closed: duplicate)">#2778</a>.
</p>
TicketburcinSat, 18 Jun 2011 01:10:50 GMT
https://trac.sagemath.org/ticket/11309#comment:30
https://trac.sagemath.org/ticket/11309#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:26" title="Comment 26">tnv</a>:
</p>
<blockquote class="citation">
<p>
From your msg, would it be reasonable to add a SMT theorem prover package to Sage ? So that it can show equivalence of expressions (at least under some specific theories).
</p>
</blockquote>
<p>
Sage is really large as it is. While I'd be really interested to have this capability in Sage, I don't know how many others would want it in the standard distribution. The first step is to start with an optional package/prototype. We can see where it goes from there. :)
</p>
<p>
Which prover are you thinking of? What would this let us do in Sage? Perhaps you should write a message to sage-devel about this.
</p>
TickettnvSat, 18 Jun 2011 01:33:20 GMT
https://trac.sagemath.org/ticket/11309#comment:31
https://trac.sagemath.org/ticket/11309#comment:31
<blockquote class="citation">
<p>
Which prover are you thinking of? What would this let us do in Sage? Perhaps you should write a message to sage-devel about this.
</p>
</blockquote>
<p>
I am thinking about the optional package too. Someone told me qepcad (not exactly SMT but can be used for many similar purpose) already in Sage as an optional package.
</p>
<p>
The good thing about these SMT solvers is that most of them support a standard language (smtlib) and therefore you can use any of the SMT's out there with a single interface. SMT can be used to show if something (a set of expressions or constraints) is valid or satisfiable under different types of theories (not just boolean), or simplify a set of expression, etc. I rely on these for implications on my project-- to see if 2 sets of expressions are equi-satisfiable .
</p>
<p>
So all the above examples of whether if exp1 == exp2 should be easily answered with SMT.
</p>
TicketburcinSat, 18 Jun 2011 02:05:08 GMT
https://trac.sagemath.org/ticket/11309#comment:32
https://trac.sagemath.org/ticket/11309#comment:32
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:31" title="Comment 31">tnv</a>:
</p>
<blockquote class="citation">
<p>
So all the above examples of whether if exp1 == exp2 should be easily answered with SMT.
</p>
</blockquote>
<p>
I'd really like to see Sage have it's own framework to handle assumptions (see <code>assume?</code> -- this relies completely on maxima right now), so I'm really interested in this. I'd be glad to help with the first steps of making a package, writing an interface, etc. We should have this conversation in sage-devel instead of this ticket though. ;)
</p>
TicketkcrismanFri, 11 May 2012 13:24:18 GMT
https://trac.sagemath.org/ticket/11309#comment:33
https://trac.sagemath.org/ticket/11309#comment:33
<p>
This still applies, and fixes another issue.
</p>
<pre class="wiki">
sage: c = (x-2<=0)
sage: assume(c)
sage: a = (x-1<=0)
sage: if a in sage.symbolic.assumptions._assumptions:
....: print 'yes'
....:
sage: assumptions()
[x - 2 <= 0]
sage: assume(a)
sage: assumptions()
[x - 2 <= 0, x - 1 <= 0]
</pre><p>
Before, the second assumption didn't obtain, because currently
</p>
<pre class="wiki">
sage: c = (x-2<=0)
sage: L = [c]
sage: L
[x - 2 <= 0]
sage: a = (x-1<=0)
sage: a in L
True
</pre><p>
which is not good. See <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-support/H-QcXkNCajM"><span class="icon"></span>this sage-support thread</a>.
</p>
TicketkcrismanFri, 11 May 2012 13:27:17 GMT
https://trac.sagemath.org/ticket/11309#comment:34
https://trac.sagemath.org/ticket/11309#comment:34
<p>
Since <a class="new ticket" href="https://trac.sagemath.org/ticket/2744" title="enhancement: make symbolicequations deal with logical combinations (new)">#2744</a> is on sage-wishlist, would it suffice to do some sort of "switch lhs and rhs" check as a last branch in the code to fix tnv's point in <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:21" title="Comment 21">comment:21</a> (formatted in <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:24" title="Comment 24">comment:24</a>)? It would be nice to finally resolve this at the upcoming Bug Days.
</p>
TicketppurkaFri, 11 May 2012 15:43:27 GMT
https://trac.sagemath.org/ticket/11309#comment:35
https://trac.sagemath.org/ticket/11309#comment:35
<p>
In the patch, why is this evaluated to <code>True</code>?
</p>
<div class="wiki-code"><div class="code"><pre><span class="gi">+ sage: (x < y) != (y > x)
+ True
</span></pre></div></div><p>
EDIT: Oops. I should have read the earlier comments. Sorry.
</p>
TicketkiniSat, 12 May 2012 22:55:26 GMT
https://trac.sagemath.org/ticket/11309#comment:36
https://trac.sagemath.org/ticket/11309#comment:36
<p>
kcrisman: OK, I'll try to implement those minimal checks for now, and we can do nesting expressions later.
</p>
TicketkiniSun, 13 May 2012 01:20:04 GMTstatus, description changed
https://trac.sagemath.org/ticket/11309#comment:37
https://trac.sagemath.org/ticket/11309#comment:37
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11309?action=diff&version=37">diff</a>)
</li>
</ul>
<p>
Added a new patch. Burcin, can you look over it to make sure I'm doing this the right way? In particular are those operator comparisons optimizable somehow?
</p>
TicketkiniSun, 13 May 2012 01:24:55 GMT
https://trac.sagemath.org/ticket/11309#comment:38
https://trac.sagemath.org/ticket/11309#comment:38
<p>
Update: added three more lines to the doctests
</p>
TicketkiniMon, 14 May 2012 05:52:15 GMT
https://trac.sagemath.org/ticket/11309#comment:39
https://trac.sagemath.org/ticket/11309#comment:39
<p>
Hey patchbot:
</p>
<p>
Apply trac_11309-fix-comparison-of-comparisons.patch trac_11309-equate-flipped-comparisons.patch
</p>
TicketkcrismanMon, 14 May 2012 18:15:04 GMT
https://trac.sagemath.org/ticket/11309#comment:40
https://trac.sagemath.org/ticket/11309#comment:40
<p>
The code itself seems fine right now, thanks for such fast action and especially for actual comments in the code!
</p>
<p>
Did you do any timing runs on previously-working comparisons? I agree that it would be good for someone who knows to comment on whether there is some obvious optimization missing. For instance, lines 1241ff. would be nicer if it so happened there was a "operator.opposite()" function which reversed <code><=</code> and <code>>=</code> (though someone else might want them to be complements, <code><=</code> and <code>></code>). Similarly for the rhs/lhs comparisons.
</p>
<p>
Keshav, do you mind putting in a test in your patch for
</p>
<pre class="wiki">sage: (x-1<0) in [x-2<0]
False
</pre><p>
just to test for the <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:33" title="Comment 33">comment:33</a> issue? While we wait for someone more knowledgeable... but as I said it does seem good to go.
</p>
TicketkiniMon, 14 May 2012 18:51:16 GMTattachment set
https://trac.sagemath.org/ticket/11309
https://trac.sagemath.org/ticket/11309
<ul>
<li><strong>attachment</strong>
set to <em>trac_11309-equate-flipped-comparisons.patch</em>
</li>
</ul>
<p>
apply to $SAGE_ROOT/devel/sage
</p>
TicketkiniMon, 14 May 2012 19:01:04 GMT
https://trac.sagemath.org/ticket/11309#comment:41
https://trac.sagemath.org/ticket/11309#comment:41
<p>
Done! Glad you like the comments :)
</p>
<p>
I did not do any timing, no. I'm not sure what you mean by "lines 1241ff", but function calls should typically be avoided if you're optimizing for speed, afaik. The main thing I was wondering was, the argument <code>op</code> to the function <code>_richcmp_c_impl()</code> is an integer, but <code>operator.*</code> as seen in lines 1245-1252 seem to be strings, if I'm not mistaken. So I'm just wondering if that many string operations for a single comparison of symbolic expression couldn't be better optimized by somehow getting the operator of the lhs and rhs of the big relation as integers rather than strings. Well, not to mention that I'm calling <code>.operator()</code> a bunch of times, but I don't know if it would actually be any faster to compute it once and store it in a variable.
</p>
<p>
They say you shouldn't try to second-guess compilers... I guess the best way to find out is to try a few different ways and see how <code>timeit</code> behaves. I'll do that later, I guess...
</p>
TicketkiniMon, 14 May 2012 19:02:11 GMT
https://trac.sagemath.org/ticket/11309#comment:42
https://trac.sagemath.org/ticket/11309#comment:42
<p>
Hey patchbot:
</p>
<p>
Apply trac_11309-fix-comparison-of-comparisons.patch trac_11309-equate-flipped-comparisons.patch
</p>
TicketkcrismanFri, 25 May 2012 14:50:32 GMTkeywords changed
https://trac.sagemath.org/ticket/11309#comment:43
https://trac.sagemath.org/ticket/11309#comment:43
<ul>
<li><strong>keywords</strong>
<em>sd40.5</em> added
</li>
</ul>
<p>
I guess there isn't any reason to put this off, unless the timing issue really is a biggie. Did you want to run a few of them first?
</p>
TicketkcrismanFri, 25 May 2012 15:34:13 GMT
https://trac.sagemath.org/ticket/11309#comment:44
https://trac.sagemath.org/ticket/11309#comment:44
<p>
Hmm, this is a big slowdown in at least one case.
</p>
<pre class="wiki"># old
sage: timeit("(x < y) != (y > x)")
625 loops, best of 3: 2.76 µs per loop
# new
sage: timeit("(x < y) != (y > x)")
625 loops, best of 3: 13.3 µs per loop
</pre><p>
It looks like it's fairly constantly adding this. Here, in the much slower checking of a list
</p>
<pre class="wiki"># old
sage: timeit("(x - 1 < 0) in [x - 2 < 0]")
625 loops, best of 3: 104 µs per loop
# new
sage: timeit("(x - 1 < 0) in [x - 2 < 0]")
625 loops, best of 3: 116 µs per loop
</pre><p>
Here's another one.
</p>
<pre class="wiki"># old
sage: timeit("(y > y) != (y > y) ")
625 loops, best of 3: 2.24 µs per loop
# new
sage: timeit("(y > y) != (y > y) ")
625 loops, best of 3: 8.45 µs per loop
</pre>
TicketkiniSat, 26 May 2012 07:17:29 GMT
https://trac.sagemath.org/ticket/11309#comment:45
https://trac.sagemath.org/ticket/11309#comment:45
<p>
I'm kind of OK with this slowdown. It's in the low microseconds range, and it's also understandable considering the new code actually checks some stuff, whereas the old code doesn't really.
</p>
<p>
I guess I will ping Burcin about this via email.
</p>
TicketkiniMon, 28 May 2012 22:18:33 GMT
https://trac.sagemath.org/ticket/11309#comment:46
https://trac.sagemath.org/ticket/11309#comment:46
<p>
Burcin says he's too busy to look carefully but that the code probably can't be optimized much further.
</p>
TicketkiniMon, 28 May 2012 22:21:20 GMTsummary changed
https://trac.sagemath.org/ticket/11309#comment:47
https://trac.sagemath.org/ticket/11309#comment:47
<ul>
<li><strong>summary</strong>
changed from <em>Sage sees -x +y > 0, -y + x >= 0, and x -y > 0 as equivalent</em> to <em>Sage sees - x + y > 0, - y + x >= 0, and x - y > 0 as equivalent</em>
</li>
</ul>
TicketkcrismanMon, 28 May 2012 22:34:14 GMTstatus changed
https://trac.sagemath.org/ticket/11309#comment:48
https://trac.sagemath.org/ticket/11309#comment:48
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<blockquote class="citation">
<p>
Burcin says he's too busy to look carefully but that the code probably can't be optimized much further.
</p>
</blockquote>
<p>
Good enough for me.
</p>
TicketkiniMon, 28 May 2012 22:57:03 GMT
https://trac.sagemath.org/ticket/11309#comment:49
https://trac.sagemath.org/ticket/11309#comment:49
<p>
Thanks!
</p>
TickettnvThu, 31 May 2012 06:10:02 GMT
https://trac.sagemath.org/ticket/11309#comment:50
https://trac.sagemath.org/ticket/11309#comment:50
<p>
I am interested in trying this patch but not sure how to apply it correctly. This is what I did on Sage 5.0 (Mac OS Snow Leopard)
</p>
<pre class="wiki">$ pwd
/Users/tnguyen/Src/Devel/SAGE/sage-5.0/devel/sage
$ sage -hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/11309/trac_11309-equate-flipped-comparisons.patch
adding trac_11309-equate-flipped-comparisons.patch to series file
Godel Wed May 30:23:05:42 (4714) ~/Src/Devel/SAGE/sage-5.0/devel/sage
$ sage -hg qpushapplying trac_11309-equate-flipped-comparisons.patch
patching file sage/symbolic/expression.pyx
Hunk #1 FAILED at 1179
Hunk #2 FAILED at 1186
Hunk #3 FAILED at 1204
3 out of 3 hunks FAILED -- saving rejects to file sage/symbolic/expression.pyx.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_11309-equate-flipped-comparisons.patch
Godel Wed May 30:23:05:51 (4715) ~/Src/Devel/SAGE/sage-5.0/devel/sage
</pre>
TicketppurkaThu, 31 May 2012 06:34:49 GMT
https://trac.sagemath.org/ticket/11309#comment:51
https://trac.sagemath.org/ticket/11309#comment:51
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:50" title="Comment 50">tnv</a>:
</p>
<blockquote class="citation">
<p>
I am interested in trying this patch but not sure how to apply it correctly.
</p>
</blockquote>
<p>
You need to apply both the patches <em>in the order mentioned in the description of this ticket</em>. Try these commands (assuming you are in devel/sage)
</p>
<pre class="wiki">../../sage -hg qimport -P http://trac.sagemath.org/sage_trac/raw-attachment/ticket/11309/trac_11309-fix-comparison-of-comparisons.patch
../../sage -hg qimport -P http://trac.sagemath.org/sage_trac/raw-attachment/ticket/11309/trac_11309-equate-flipped-comparisons.patch
../../sage -br
</pre>
TicketkiniThu, 31 May 2012 07:30:31 GMT
https://trac.sagemath.org/ticket/11309#comment:52
https://trac.sagemath.org/ticket/11309#comment:52
<p>
Patchbot: Apply trac_11309-fix-comparison-of-comparisons.patch trac_11309-equate-flipped-comparisons.patch
</p>
TickettnvThu, 31 May 2012 20:45:55 GMT
https://trac.sagemath.org/ticket/11309#comment:53
https://trac.sagemath.org/ticket/11309#comment:53
<p>
Hi, may be I've missed something but these patches still break things as listed in my <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:24" title="Comment 24">comment:24</a>.
</p>
<pre class="wiki">(prepatched)
sage: (- x + y == 0) == (0 == -x + y)
True
sage: (-x + y == 0) == (0 == -x + y)
True
sage: (x < y) == (y > x)
True
(postpatched)
sage: (- x + y == 0) == (0 == -x + y)
False
sage: (-x + y == 0) == (0 == -x + y)
False
sage: (x < y) == (y > x)
False
</pre><p>
The main reason why I report this in the first place is because of this error in which multiplying by -1 does not switch the sign. I think they are related but not sure.
</p>
<pre class="wiki">sage: -1 * (x<5)
-x < -5
</pre>
TicketkiniThu, 31 May 2012 21:03:17 GMT
https://trac.sagemath.org/ticket/11309#comment:54
https://trac.sagemath.org/ticket/11309#comment:54
<p>
Did you forget to rebuild Sage after applying the patches?
</p>
<pre class="wiki">[1] fs-boone@zhenghe /opt/sage/devel/sage $ hg qapplied
trac_13057-no-intersphinx.patch
trac_11309-fix-comparison-of-comparisons.patch
trac_11309-equate-flipped-comparisons.patch
[1] fs-boone@zhenghe /opt/sage/devel/sage $ sage -b &> /dev/null
[1] fs-boone@zhenghe /opt/sage/devel/sage $ sage -q
sage: var('y')
y
sage: (- x + y == 0) == (0 == -x + y)
True
sage: (-x + y == 0) == (0 == -x + y)
True
sage: (x < y) == (y > x)
True
sage: -(x < 5)
-x < -5
sage:
</pre><p>
Personally I don't see why <code>x * (y < z)</code> should even be simplified to anything other than <code>x * (y < z)</code>. <code>y < z</code> is a mathematical object which does not live in a space which has a multiplication operation - it lives in the space of logical predicates. But that is something to address in a different ticket. Testing the title of this ticket:
</p>
<pre class="wiki">sage: Set([-x + y > 0, -y + x >= 0, x - y > 0])
{-x + y > 0, x - y >= 0, x - y > 0}
sage: len(_)
3
</pre><p>
So the patches do at least address and solve the issue in the ticket's name.
</p>
TicketburcinFri, 01 Jun 2012 10:01:03 GMT
https://trac.sagemath.org/ticket/11309#comment:55
https://trac.sagemath.org/ticket/11309#comment:55
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11309#comment:53" title="Comment 53">tnv</a>:
</p>
<blockquote class="citation">
<p>
The main reason why I report this in the first place is because of this error in which multiplying by -1 does not switch the sign. I think they are related but not sure.
</p>
<pre class="wiki">sage: -1 * (x<5)
-x < -5
</pre></blockquote>
<p>
This is <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/7660" title="defect: arithmetic with equations and inequalities confusing (needs_work)">#7660</a>. It would be quite easy to remove the <code>if is_a_relational(left._gobj)</code> checks in <code>_add_, </code>_mul_<code>, etc. in </code>sage/symbolic/expression.pyx` to revert back to GiNaC behavior.
</p>
TickettnvFri, 01 Jun 2012 20:05:45 GMT
https://trac.sagemath.org/ticket/11309#comment:56
https://trac.sagemath.org/ticket/11309#comment:56
<p>
It seems to work fine now -- not sure what I did previously. So if you don't use hash for comparison , what do you use ? Thanks all of those who spend time to create these patches.
</p>
TicketkiniFri, 01 Jun 2012 20:56:13 GMT
https://trac.sagemath.org/ticket/11309#comment:57
https://trac.sagemath.org/ticket/11309#comment:57
<p>
Given two relational expressions <code>a ? b</code> and <code>c ! d</code>, first I check whether <code>?</code> and <code>!</code> are the same relation. If so, I have a couple of cases. One, if <code>?</code> and <code>!</code> are both <code>==</code> or are both <code>!=</code>, then I check whether <code>a == c</code> and <code>b == d</code>, or <code>a == d</code> and <code>b == c</code>. Two, if <code>?</code> and <code>!</code> are some other relation than <code>==</code> or <code>!=</code>, then I only allow the case <code>a == c</code> and <code>b == d</code>.
</p>
<p>
If <code>?</code> and <code>!</code> are different from each other, I check whether they are reversals of each other (like one is <code><</code> and the other is <code>></code>, etc.). If that is the case, then I allow <code>a == d</code> and <code>b == c</code>.
</p>
<p>
In all other cases, the two relational expressions are considered unequal.
</p>
<p>
... that explanation looks kind of confusing. Maybe it's better if you just look at the patch... it's probably easier to understand :)
</p>
TicketjdemeyerTue, 05 Jun 2012 11:50:48 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11309#comment:58
https://trac.sagemath.org/ticket/11309#comment:58
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.1.beta3</em>
</li>
</ul>
Ticket