login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Submitted by : (unknown) at: 2007-11-17T22:05:44-08:00 (9 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

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

\label{eq1}1(1)
Type: UnivariatePolynomial(x,Expression(Integer))

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

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

\label{eq2}x -{{2}^{a}}(2)
Type: UnivariatePolynomial(x,Expression(Integer))

In fact, to ensure that algebraic relations are respected inside expressions one has to normalize all involved expressions:

fricas
uP := UP(x, EXPR INT)

\label{eq3}\hbox{\axiomType{UnivariatePolynomial}\ } (x , \hbox{\axiomType{Expression}\ } (\hbox{\axiomType{Integer}\ }))(3)
Type: Type
fricas
p1 := (x-2^a)::uP

\label{eq4}x -{{2}^{a}}(4)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
p2 := simplify((x-2^a)*(x+2^a))::uP

\label{eq5}{{x}^{2}}-{{4}^{a}}(5)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
cl1 := coefficients(p1)

\label{eq6}\left[ 1, \: -{{2}^{a}}\right](6)
Type: List(Expression(Integer))
fricas
cl2 := coefficients(p2)

\label{eq7}\left[ 1, \: -{{4}^{a}}\right](7)
Type: List(Expression(Integer))
fricas
ncl := normalize(concat(cl1, cl2))

\label{eq8}\left[ 1, \: -{{e}^{a \ {\log \left({2}\right)}}}, \: 1, \: -{{{e}^{a \ {\log \left({2}\right)}}}^{2}}\right](8)
Type: List(Expression(Integer))
fricas
ncl1 := first(ncl, #cl1)

\label{eq9}\left[ 1, \: -{{e}^{a \ {\log \left({2}\right)}}}\right](9)
Type: List(Expression(Integer))
fricas
ncl2 := rest(ncl, #cl1)

\label{eq10}\left[ 1, \: -{{{e}^{a \ {\log \left({2}\right)}}}^{2}}\right](10)
Type: List(Expression(Integer))
fricas
np1 := reduce(_+, [monomial(c,degree(m))$uP for m in monomials(p1) for c in ncl1])

\label{eq11}x -{{e}^{a \ {\log \left({2}\right)}}}(11)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
np2 := reduce(_+, [monomial(c,degree(m))$uP for m in monomials(p2) for c in ncl2])

\label{eq12}{{x}^{2}}-{{{e}^{a \ {\log \left({2}\right)}}}^{2}}(12)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
gcd(np1, np2)

\label{eq13}x -{{e}^{a \ {\log \left({2}\right)}}}(13)
Type: UnivariatePolynomial(x,Expression(Integer))

Not nice, but in general this is what is needed (below are simpler attempts which sometimes work, but may fail).

Internal Cause

In EXPR INT, 4^a and 2^{(2a)} are treated as two variables without relations in EXPR INT. But

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

\label{eq14}{{x}^{2}}-{{4}^{a}}(14)
Type: UnivariatePolynomial(x,Expression(Integer))

Therefore exquo in:

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

fails. In details, it calls exquo$UP(x,EXPR INT). This implements exact division of polynomials p1 by p2 as usual. After each subtraction - done via fmecg$UP - the result is again stored in p1. exquo terminates when p1 is the empty list - note that UPs? 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 FriCAS does not know it. In particular, p1 is not the empty list, but rather a constant polynomial...

To get correct result we need to express coefficients of p1 and p2 in terms of independent kernels. In more general contexts (in particular involving abs) this is undecidable, but for elementary functions normalize works. More precisely, currently normalize ignores possible dependencies between algebraic quantities like roots. And to simplification of transcendental constants depends on Schanuel conjecture (if Schanuel conjecture is false we may miss some dependencies).

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

I should have added:

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

\label{eq15}{{{e}^{a \ {\log \left({4}\right)}}}-{{A}^{2}}}\over{{{e}^{a \ {\log \left({2}\right)}}}- A}(15)
Type: Union(Expression(Integer),...)
fricas
exquo(simplify((A-2^a)*(A+2^a))::UP(A,EXPR INT),(A-2^a)::UP(A,EXPR INT))

\label{eq16}\verb#"failed"#(16)
Type: Union("failed",...)

This shows that using normalize separately on polynomials does not help, we need to normalize list of coefficients as a whole.

Few examples showing that without normalization FriCAS does not always treat 2^{a2} the same as 4^a:

fricas
dom:=UP('x,EXPR INT)

\label{eq17}\hbox{\axiomType{UnivariatePolynomial}\ } (x , \hbox{\axiomType{Expression}\ } (\hbox{\axiomType{Integer}\ }))(17)
Type: Type
fricas
p:dom:=x-2^a

\label{eq18}x -{{2}^{a}}(18)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
q:=(x-2^a)*(x+2^a)

\label{eq19}-{{{2}^{a}}^{2}}+{{x}^{2}}(19)
Type: Expression(Integer)
fricas
qq:= simplify(q)

\label{eq20}-{{4}^{a}}+{{x}^{2}}(20)
Type: Expression(Integer)
fricas
r:= q::dom

\label{eq21}{{x}^{2}}-{{{2}^{a}}^{2}}(21)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
rr:= qq::dom

\label{eq22}{{x}^{2}}-{{4}^{a}}(22)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
gcd(p,q)

\label{eq23}x -{{2}^{a}}(23)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
exquo(q,p)

\label{eq24}{{2}^{a}}+ x(24)
Type: Union(Expression(Integer),...)
fricas
gcd(p,r)

\label{eq25}x -{{2}^{a}}(25)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
gcd(p,qq)

\label{eq26}1(26)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
gcd(p,rr)

\label{eq27}1(27)
Type: UnivariatePolynomial(x,Expression(Integer))
fricas
q - qq

\label{eq28}{{4}^{a}}-{{{2}^{a}}^{2}}(28)
Type: Expression(Integer)
fricas
simplify q - qq

\label{eq29}0(29)
Type: Expression(Integer)
fricas
simplify ((r - rr)::EXPR INT)

\label{eq30}0(30)
Type: Expression(Integer)
fricas
t:Boolean:=(r = rr)

\label{eq31} \mbox{\rm false} (31)
Type: Boolean

Status: open => closed




  Subject:   Be Bold !!
  ( 13 subscribers )  
Please rate this page: