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