Re: need help with writing algorithm for polynomial gcd!
- To: mathgroup at smc.vnet.net
- Subject: [mg46699] Re: need help with writing algorithm for polynomial gcd!
- From: astanoff at yahoo.fr (astanoff)
- Date: Tue, 2 Mar 2004 00:14:22 -0500 (EST)
- References: <c1ltma$nq3$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Tina Fisher wrote:
> I know MATHEMATICA has a built in function to computer the polynomial
> GCD ...
> but:
> what if I need to write a small M-program that does the following:
> given two polynomials in the form [a0,a1, ..., ak], [b0,b1,...bj] -
> i.e. coefficients only
> now compute the polynomial gcd (we only consider real numbers, no
> finite fields or evil stuff...! ... that is the good part!)
> what would be an efficient algorithm to do this?
[...]
This is no use and not very efficient, but it works :
In[1]:=
myGCD[p1_List,p2_List]:=
Module[{mon,x,pol1,pol2,num},
mon[a_,{b_}]:=a*x^(b-1);
pol1=Factor[Plus@@MapIndexed[mon,p1]];
pol2=Factor[Plus@@MapIndexed[mon,p2]];
num=Numerator[pol1/pol2];
CoefficientList[pol1/num,x]
];
In[2]:=
myGCD[{1,1,-2,-2,1,1},{-2,-3,1,3,1}]
Out[2]=
{-1,-1,1,1}
--