CODEWITHSUNDEEP
algorithmmaple
Dawn Chumley
Dawn Chumley

Reputation: 1

Extended Euclidean Algorithm in Maple

This is my code for the Extended Euclidean Algorithm in Maple, which should return integer l, polynomials pi,ri,si,ti for 0<=i<=l+1. And polynomial qi for 1<=i<=l such that si(f)+ti(g) = ri and sl(f)+tl(g)=rl=GCD(f,g).

The problem is, I keep getting division by zero. Also it evaluates pi = lcoeff(ri-1 - qiri) to be zero, everytime. Even when I remove this it still says there is a division of zero, which must be coming from qi:=quo(ri-1,ri, x); however I do not know why considering the requirements for the loop are that r[i] not equal zero. I really could use a fresh pair of eyes to see what I've done wrong.

ExtEuclidean := proc (f, g) local p, r, s, t, i, q, l;
p[0] := lcoeff(f); 
p[1] := lcoeff(g); 
r[0] := f/p[0]; 
r[1] := g/p[1]; 
s[0] := 1; 
s[1] := 0; 
t[0] := 0; 
t[1] := 1; 
i := 1; 
while r[i] <> 0 do 
l := i; 
q[i] := quo(r[i-1], r[i], x, 'remainder');
simplify(q[i]); 
p[i+1] := lcoeff(r[i-1]-q[i]*r[i]);
r[i+1] := (r[i-1]-q[i]*r[i])/p[i+1]; 
s[i+1] := (s[i-1]-q[i]*s[i])/p[i+1]; 
t[i+1] := (t[i-1]-q[i]*t[i])/p[i+1]; 
i := i+1; 
simplify(r[i]) 
end do; 
return l, p[i], r[i], s[i], t[i], q[i] 
end proc;

Upvotes: 0

Views: 959

Answers (1)

Matt
Matt

Reputation: 11

It looks like something wrong with your indexing. I didn't think too hard, but this seems to work on basic examples. I changed p[i+1] to p[i] in the loop and altered the output

ExtEuclidean := proc (f, g) local p, r, s, t, i, q, l;
    p[0] := lcoeff(f); 
    p[1] := lcoeff(g); 
    r[0] := f/p[0]; 
    r[1] := g/p[1]; 
    s[0] := 1; 
    s[1] := 0; 
    t[0] := 0; 
    t[1] := 1; 
    i := 1; 
    while r[i] <> 0 do 
    l := i; 
    q[i] := quo(r[i-1], r[i], x, 'remainder');
    simplify(q[i]); 
    p[i+1] := lcoeff(r[i-1]-q[i]*r[i]);
    r[i+1] := (r[i-1]-q[i]*r[i])/p[i]; 
    s[i+1] := (s[i-1]-q[i]*s[i])/p[i]; 
    t[i+1] := (t[i-1]-q[i]*t[i])/p[i]; 
    i := i+1; 
    simplify(r[i]) 
    end do; 
    return l, p[i-1], r[i-1], s[i-1], t[i-1], q[i-1] 
    end proc;

Upvotes: 1

Related Questions