Menu
▾
▴
#365 orderlessp not transitive
l: [z+x*(x+2)+v+1,z+x^2+x+v+1,z+(x+1)^2+v];
orderlessp(l[1],l[2]) => True
orderlessp(l[2],l[3]) => True
orderlessp(l[1],l[3]) => False !!!
More concise example:
q: x^2;
r: (x+1)^2;
s: x*(x+2);
orderlessp(q,r) => true
orderlessp(r,s) => true
orderlessp(s,q) => true
That is, s<q<r<s.
The problem is somewhere in the internal great function,
which by the way does some strange things, in
particular: why does ordlist have an explicit check for
mplus: (RETURN (COND ((= L2 0) (EQ CX 'MPLUS))
(Thanks to Barton for his contributions to tracking this
down.)
Maxima 5.9.0 GCL 2.5.0
Logged In: YES
user_id=588346
This not only screws up SORT etc., but even basic
simplification, since simplus, simptimes, etc. depend on great:
q+r+s => (x+1)^2+x^2+x*(x+2)
q+s+r => x^2+x*(x+2)+(x+1)^2
(q+s+r)-(q+s+r) => x^2-x^2
(q+s+r)-(s+q+r) => x^2-x^2
(q+r+s)-(q+s+r) => x (x + 2) - x (x + 2)
Logged In: YES
user_id=588346
More amusing consequences:
q+r+s => (x+1)^2+x^2+x*(x+2)
expand(%,0,0) => x^2+x*(x+2)+(x+1)^2
expand(%,0,0) => x*(x+2)+(x+1)^2+x^2
expand(%,0,0) => (x+1)^2+x^2+x*(x+2)
q+r+s-r-q-s => (x+1)^2+x^2+x*(x+2)-(x+1)^2-x^2-x*
(x+2)
expand(%,0,0) => x^2-x^2
expand(%,0,0) => 0
I haven't found an example where simptimes fails, though.
Fateman reports that this bug is also found in commercial
Macsyma 2.4, and calls it a Methuselah bug because it has
persisted for so long -- presumably it has been around for 30+
years.
Logged In: YES
user_id=581700
This one doesn't even involve MEXPT (I found it while checking one of
the cases needed for proving that ORDLIST implements a consistent way
of extending a given total order on a set of simplified expressions to
their simplified sums and products. So it doesn't...)
(C1) orderlessp(t/2,t);
(D1) TRUE
(C2) orderlessp(t,t+1/4);
(D2) TRUE
(C3) orderlessp(t/2,t+1/4);
(D3) FALSE
The point is that t/2 is ((MTIMES SIMP) ((RAT SIMP) 1 2) |$t|) and,
lexicographically, we have (t, 1/2) < (t, 1), (t, 0) < (t, 1/4) and
(t, 1/2, *) > (t, 1/4, +). So t corresponds to (t, 1) in the first
comparison and to (t, 0) in the second comparison. Trouble.
Floats instead of rational numbers give the same results, by the way.
This one is more like Stavros's examples.
(C1) orderlessp((x+1)^2,x^2-1);
(D1) TRUE
(C2) orderlessp(x^2-1,x^2);
(D2) TRUE
(C3) orderlessp((x+1)^2,x^2);
(D3) FALSE
Maybe powers whose exponents are positive integers should be treated
like products. Actually, ORDMEXPT does this already but it isn't
always called by ORDFN, for whatever reason. Anyway, here is the
patch I'm currently experimenting with (it solves all the issues
reported by Stavros and also the last example above, but in light of
the other example it is certainly far from being a complete solution.
It might even be totally wrong since I have no reason to believe that
it is more than a simple palliative and that it would make things more
consistent).
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cut ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Index: simp.lisp
===================================================================
RCS file: /cvsroot/maxima/maxima/src/simp.lisp,v
retrieving revision 1.5
diff -C2 -r1.5 simp.lisp
*** simp.lisp 5 Mar 2003 01:36:26 -0000 1.5
--- simp.lisp 8 Aug 2003 19:10:57 -0000
***************
*** 1848,1854 ****
((MEMQ CX '(MPLUS MTIMES))
(COND ((MEMQ CY '(MPLUS MTIMES)) (ORDLIST (CDR X) (CDR Y) CX CY))
! ((ALIKE1 (SETQ U (CAR (LAST X))) Y) (NOT (ORDHACK X)))
! ((AND (EQ CX 'MPLUS) (EQ CY 'MEXPT) (MPLUSP (CADR Y)))
(NOT (ORDMEXPT Y X)))
(T (GREAT U Y))))
((MEMQ CY '(MPLUS MTIMES)) (NOT (ORDFN Y X)))
--- 1848,1854 ----
((MEMQ CX '(MPLUS MTIMES))
(COND ((MEMQ CY '(MPLUS MTIMES)) (ORDLIST (CDR X) (CDR Y) CX CY))
! ((AND (EQ CX 'MPLUS) (EQ CY 'MEXPT))
(NOT (ORDMEXPT Y X)))
+ ((ALIKE1 (SETQ U (CAR (LAST X))) Y) (NOT (ORDHACK X)))
(T (GREAT U Y))))
((MEMQ CY '(MPLUS MTIMES)) (NOT (ORDFN Y X)))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cut ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Logged In: YES
user_id=501686
Increasing the priority on this one -- potential for subtle
breakage in various contexts.
I think these issues are resolved in simp.lisp rev 1.93.
This Tracker item was closed automatically by the system. It was
previously set to a Pending status, and the original submitter
did not respond within 14 days (the time period specified by
the administrator of this Tracker).