#365 orderlessp not transitive

closed
nobody
Lisp Core (471)
7
2009-12-28
2003-07-23
No

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

Discussion

  • Stavros Macrakis

    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)

     
  • Stavros Macrakis

    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.

     
  • Wolfgang Jenkner

    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 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

     
  • Robert Dodier

    Robert Dodier - 2006-07-08
    • labels: --> Lisp Core
     
  • Robert Dodier

    Robert Dodier - 2006-07-08

    Logged In: YES
    user_id=501686

    Increasing the priority on this one -- potential for subtle
    breakage in various contexts.

     
  • Robert Dodier

    Robert Dodier - 2006-07-08
    • priority: 5 --> 7
     
  • Dan Gildea

    Dan Gildea - 2009-12-14

    I think these issues are resolved in simp.lisp rev 1.93.

     
  • Dan Gildea

    Dan Gildea - 2009-12-14
    • status: open --> pending
     
  • SourceForge Robot

    • status: pending --> closed
     
  • SourceForge Robot

    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).

     

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks