login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit
IssueTracker
#190 Compile fail on Fedora Core 4  ← ↑ →  #192 Folding does not work in Konqueror 3.1.4

#191 exquo and therefore gcd cannot handle UP(x, EXPR INT)
  
last edited 7 years ago by test1

Edit detail for #191 exquo and therefore gcd cannot handle UP(x, EXPR INT) revision 1 of 6
1 2 3 4 5 6
Editor:
Time: 2007/11/17 22:05:44 GMT-8
Note: 
changed:
-
From BillPage Mon Jul 11 15:56:25 -0500 2005
From: Bill Page
Date: Mon, 11 Jul 2005 15:56:25 -0500
Subject: (new) exquo and therefore gcd cannot handle UP(x, EXPR INT)
Message-ID: <20050711-205617.sv12157.86660@savannah.nongnu.org>


Update of bug #10530 (project axiom):

                  Status:                    None => transferred            

\begin{axiom}
gcd((x-2^a)::UP(x, EXPR INT), simplify((x-2^a)*(x+2^a))::UP(x, EXPR INT))
\end{axiom}

Gives 1, while the correct answer should be $x-2^a$, as given by

\begin{axiom}
gcd((x-2^a)::UP(x, EXPR INT),((x-2^a)*(x+2^a))::UP(x, EXPR INT))
\end{axiom}

	gcd((x-2^a)::UP(x, EXPR INT), simplify((x-2^a)*(x+2^a))::UP(x, EXPR INT))

gives 1, while the correct answer should be x-2^a, as given by

gcd((x-2^a)::UP(x, EXPR INT),((x-2^a)*(x+2^a))::UP(x, EXPR INT))

A workaround is presented on [EXPR_GCD]

Internal Cause

  In EXPR INT, $2^a$ and $2^{(2a)}$ are treated as two variables
without relations in EXPR INT. Therefore exquo in::

  gcdPrimitive(p1:SUPP,p2:SUPP)$PGCD

fails.

Thu 09/30/2004 at 09:31, comment !#3

Excuse me, I was to quick again. Here is the (hopefully correct)
anaylysis::

  exquo(simplify((A-2^a)*(A+2^a))::UP(A,EXPR INT),(A-2^a)::UP(A,EXPR INT))

calls 'exquo$SUP(EXPR INT)'. This implements exact division of
polynomials p1 by p2 as usual. After each subtraction - done via
'fmecg$SUP' - the result is again stored in p1. exquo terminates
when p1 is the empty list - note that SUPs are stored as lists
of pairs (degree, coefficient) - or the degree of p2 is larger
than p1. In the latter case, exquo fails.

Thus, in our case, at one point p1 is $4^a-2^{(2a)}$, which is zero
mathematically, but axiom does not know it. In particular,
p1 is not the empty list, but rather a constant polynomial...

It would be interesting to see how MuPAD or Aldor handle this.

Martin Rubey <kratt6>

Wed 09/29/2004 at 16:20, comment !#2:

  The instance of exquo involved is the one in SMP.

Sorry, this is not correct. It is in FIELD (for EXPR INT)

Martin Rubey <kratt6>

Wed 09/29/2004 at 16:02, comment !#1:

  I should have added:

\begin{axiom}
exquo(normalize(simplify(((A-2^a)*(A+2^a)))::EXPR INT),normalize((A-2^a)::EXPR INT))
exquo(simplify((A-2^a)*(A+2^a))::UP(A,EXPR INT),(A-2^a)::UP(A,EXPR INT))
\end{axiom}

I'm afraid that this cannot be fixed easily, since there is no
general mechanism to determine whether an expression is zero or not,
which is needed in exquo. The instance of exquo involved is the
one in SMP.

From billpage Wed Jul 13 00:47:27 -0500 2005
From: billpage
Date: Wed, 13 Jul 2005 00:47:27 -0500
Subject: $2^{{a2}}$ vs $4^a$
Message-ID: <20050713004727-0500@page.axiom-developer.org>

The problem seems to be that Axiom does not always treat $2^{a2}$
the same as $4^a$.

\begin{axiom}
dom:=UP('x,EXPR INT)
p:dom:=x-2^a
q:=(x-2^a)*(x+2^a)
qq:= simplify(q)
r:= q::dom
rr:= qq::dom
gcd(p,q)
exquo(q,p)
gcd(p,r)
gcd(p,qq)
gcd(p,rr)
q - qq
simplify q - qq
simplify ((r - rr)::EXPR INT)
t:Boolean:=(r = rr)
\end{axiom}

Comments from wyscc:

Martin wrote:
> I'm afraid that this cannot be fixed easily, since there is no
> general mechanism to determine whether an expression is zero or not,
> which is needed in exquo.

Your analysis seems to be the correct diagnosis. The problem has nothing to do with 'gcd' or 'exquo', but with the fact that simplification is an art as there is no canonical form for expressions and hence no way to test equality (which is in general *different* from testing zero, a special case needed for 'exquo'). More frequent use of simplification will help but will not eliminate the problem. Here, it is because the expressions $4^a$ and $2^{2a}$ are not handled by an automatic simplification in 'UP(x, R)' (that is, not pushed down to the level of 'R').

From billpage Tue Jul 12 22:06:08 -0500 2005
From: billpage
Date: Tue, 12 Jul 2005 22:06:08 -0500
Subject: property change
Message-ID: <20050712220608-0500@page.axiom-developer.org>

Category:  => Axiom Compiler 
Severity:  => serious 
Status:  => open

Submitted by : (unknown) at: 2007-11-17T22:05:44-08:00 (16 years ago)
Name :
Axiom Version :
Category : Severity : Status :
Optional subject :  
Optional comment :

(new) exquo and therefore gcd cannot handle UP(x, EXPR INT) --Bill Page, Mon, 11 Jul 2005 15:56:25 -0500 reply
Update of bug #10530 (project axiom):

Status: None => transferred 

axiom
gcd((x-2^a)::UP(x, EXPR INT), simplify((x-2^a)*(x+2^a))::UP(x, EXPR INT))
LatexWiki Image(1)
Type: UnivariatePolynomial?(x,Expression Integer)

Gives 1, while the correct answer should be LatexWiki Image, as given by

axiom
gcd((x-2^a)::UP(x, EXPR INT),((x-2^a)*(x+2^a))::UP(x, EXPR INT))
LatexWiki Image(2)
Type: UnivariatePolynomial?(x,Expression Integer)

gcd((x-2^a)::UP(x, EXPR INT), simplify((x-2^a)*(x+2^a))::UP(x, EXPR INT))

gives 1, while the correct answer should be x-2^a, as given by

gcd((x-2^a)::UP(x, EXPR INT),((x-2^a)*(x+2^a))::UP(x, EXPR INT))

A workaround is presented on [EXPR_GCD]?

Internal Cause

In EXPR INT, LatexWiki Image and LatexWiki Image are treated as two variables without relations in EXPR INT. Therefore exquo in::

gcdPrimitive(p1:SUPP,p2:SUPP)$PGCD

fails.

Thu 09/30/2004 at 09:31, comment #3

Excuse me, I was to quick again. Here is the (hopefully correct) anaylysis: 

  exquo(simplify((A-2^a)*(A+2^a))::UP(A,EXPR INT),(A-2^a)::UP(A,EXPR INT))

calls exquo$SUP(EXPR INT). This implements exact division of polynomials p1 by p2 as usual. After each subtraction - done via fmecg$SUP - the result is again stored in p1. exquo terminates when p1 is the empty list - note that SUPs? are stored as lists of pairs (degree, coefficient) - or the degree of p2 is larger than p1. In the latter case, exquo fails.

Thus, in our case, at one point p1 is LatexWiki Image, which is zero mathematically, but axiom does not know it. In particular, p1 is not the empty list, but rather a constant polynomial...

It would be interesting to see how MuPAD? or Aldor handle this.

Martin Rubey

Wed 09/29/2004 at 16:20, comment #2:

The instance of exquo involved is the one in SMP.

Sorry, this is not correct. It is in FIELD (for EXPR INT)

Martin Rubey

Wed 09/29/2004 at 16:02, comment #1:

I should have added:

axiom
exquo(normalize(simplify(((A-2^a)*(A+2^a)))::EXPR INT),normalize((A-2^a)::EXPR INT))
LatexWiki Image(3)
Type: Union(Expression Integer,...)
axiom
exquo(simplify((A-2^a)*(A+2^a))::UP(A,EXPR INT),(A-2^a)::UP(A,EXPR INT))
LatexWiki Image(4)
Type: Union("failed",...)

I'm afraid that this cannot be fixed easily, since there is no general mechanism to determine whether an expression is zero or not, which is needed in exquo. The instance of exquo involved is the one in SMP.

LatexWiki Image vs LatexWiki Image --billpage, Wed, 13 Jul 2005 00:47:27 -0500 reply
The problem seems to be that Axiom does not always treat LatexWiki Image the same as LatexWiki Image.

axiom
dom:=UP('x,EXPR INT)
LatexWiki Image(5)
Type: Domain
axiom
p:dom:=x-2^a
LatexWiki Image(6)
Type: UnivariatePolynomial?(x,Expression Integer)
axiom
q:=(x-2^a)*(x+2^a)
LatexWiki Image(7)
Type: Expression Integer
axiom
qq:= simplify(q)
LatexWiki Image(8)
Type: Expression Integer
axiom
r:= q::dom
LatexWiki Image(9)
Type: UnivariatePolynomial?(x,Expression Integer)
axiom
rr:= qq::dom
LatexWiki Image(10)
Type: UnivariatePolynomial?(x,Expression Integer)
axiom
gcd(p,q)
LatexWiki Image(11)
Type: UnivariatePolynomial?(x,Expression Integer)
axiom
exquo(q,p)
LatexWiki Image(12)
Type: Union(Expression Integer,...)
axiom
gcd(p,r)
LatexWiki Image(13)
Type: UnivariatePolynomial?(x,Expression Integer)
axiom
gcd(p,qq)
LatexWiki Image(14)
Type: UnivariatePolynomial?(x,Expression Integer)
axiom
gcd(p,rr)
LatexWiki Image(15)
Type: UnivariatePolynomial?(x,Expression Integer)
axiom
q - qq
LatexWiki Image(16)
Type: Expression Integer
axiom
simplify q - qq
LatexWiki Image(17)
Type: Expression Integer
axiom
simplify ((r - rr)::EXPR INT)
LatexWiki Image(18)
Type: Expression Integer
axiom
t:Boolean:=(r = rr)
LatexWiki Image(19)
Type: Boolean

Comments from wyscc:

Martin wrote:

I'm afraid that this cannot be fixed easily, since there is no general mechanism to determine whether an expression is zero or not, which is needed in exquo.

Your analysis seems to be the correct diagnosis. The problem has nothing to do with gcd or exquo, but with the fact that simplification is an art as there is no canonical form for expressions and hence no way to test equality (which is in general different from testing zero, a special case needed for exquo). More frequent use of simplification will help but will not eliminate the problem. Here, it is because the expressions LatexWiki Image and LatexWiki Image are not handled by an automatic simplification in UP(x, R) (that is, not pushed down to the level of R).

property change --billpage, Tue, 12 Jul 2005 22:06:08 -0500 reply
Category: => Axiom Compiler Severity: => serious Status: => open