Re: gcd

[macsyma <macsyma@yahoo.co.jp>]

> Karim Belabas on Fri, 09 Aug 2019 16:25:37 +0200
> ? install(RgX_gcd_simple,GG); \\ direct ERS
Thank you for introducing "RgX_gcd_simple".

> *simple* choice criterion
> we use subresultant by default
> direct ERS is used only if the field of scalars is such that
> we can rule out coefficient explosion
>From the user's point of view, it is useful to have an algorithm selection flag.

And I think it would be better if there was an option to run the two methods
simultaneously and return the faster's result.

> Bill Allombert on Fri, 09 Aug 2019 16:55:27 +0200
> liftall(subst(liftall(R),t,(k*c7+c5)*Mod(1,p7)*Mod(1,p5)))
Thank you for introducing how to use 'k'. 
Your method using the simple extension is fast for P, Q which I posted.

{p7=c7^6+c7^5+c7^4+c7^3+c7^2+c7+1;
p5=c5^4+c5^3+c5^2+c5+1;
P7=subst(p7,c7,t);
P5=subst(p5,c5,t);
[R,C7,C5,k]=polcompositum(P7,P5,3);
PP=subst(liftall(P),c5,C5)*Mod(1,R);
QQ=subst(liftall(Q),c7,C7)*Mod(1,R);
R=gcd(PP/content(PP),QQ/content(QQ));
liftall(subst(liftall(R),t,(k*c7+c5)*Mod(1,p7)*Mod(1,p5)))/pollead(R)};
time = 132 ms.

install(RgX_gcd_simple,GG);
{R=RgX_gcd_simple(P,Q);liftpol(R/pollead(R))};
time = 645 ms.

However, it seems slow for P, Q in
http://macsyma.starfree.jp/temp/PQ23.gp

{p11=polcyclo(11,c11);
p23=polcyclo(23,c23);
P11=subst(p11,c11,t);
P23=subst(p23,c23,t);
[R,C11,C23,k]=polcompositum(P11,P23,3);
PP=subst(liftall(P),c11,C11)*Mod(1,R);
QQ=subst(liftall(Q),c23,C23)*Mod(1,R);
R=gcd(PP/content(PP),QQ/content(QQ));
liftall(subst(liftall(R),t,(k*c11+c23)*Mod(1,p11)*Mod(1,p23)))/pollead(R)};
time = 11,949 ms.

{R=RgX_gcd_simple(P,Q);liftpol(R/pollead(R))};
time = 60 ms.

macsyma