Sheldon Newhouse wrote:
> Hello,
> Is there a routine which performs the Euclidean algotithm for polynomials.
>
> I.e., p, q are polynomials with degree(p) = d > degree(q) =s,
> I want to obtain
>
> p = k*q + r
> where k, r are polynomials and degree(r) < s.
>
> TIA,
> -sen
>
try looking here..
http://www.cs.berkeley.edu/~fateman/282/lects/eea.ppt
eea(u,v,x):= /* smallest gcd */
block([u1,u2,u3,v1,v2,v3,t1,t2,t3, realgcd:gcd(u,v),correction:1],
u: rat(u,x), v: rat(v,x), [u1,u2,u3]:[rat(1),rat(0),u],
[v1,v2,v3]:[rat(0),rat(1),v],
while v3#0 do
( print([v1,v2,v3]),
q: quotient(u3,v3,x),
[t1,t2,t3]: [u1,u2,u3]-q*[v1,v2,v3],
[u1,u2,u3]:[v1,v2,v3],[v1,v2,v3]:[t1,t2,t3]),
correction:realgcd/u3,
[u1*correction,u2*correction,realgcd]),