메이플의 확장 유클리드 알고리즘

Question

이것은 확장 유클리드 알고리즘에 대한 코드입니다. Maple으로, l 인 0<=i<=l+1의 다항식 pi,ri,si,ti을 반환해야합니다. 그리고 1<=i<=l에 대한 다항식 qi은 si(f)+ti(g) = ri과 sl(f)+tl(g)=rl=GCD(f,g)입니다.

문제는 계속 0으로 나눕니다. 또한 매번 pi = lcoeff(ri-1 - qiri)을 0으로 평가합니다. 비록 내가 이것을 제거한다고해도 여전히 제로의 부분이 있다고 말합니다. 이것은 qi:=quo(ri-1,ri, x);에서 오는 것입니다 만, 루프의 요구 사항을 고려할 때 왜 r[i]이 0이 아닌지 모르겠습니다. 나는 정말로 내가 한 일을보기 위해 신선한 쌍둥이를 쓸 수 있었다.

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;

Answer 1

그것은 당신의 색인에 문제처럼 보인다. 너무 열심히 생각하지는 않았지만 이것은 기본적인 예제에서 작동하는 것 같습니다. 루프에서 p [i + 1]을 p [i]로 변경하고 출력을 변경했습니다.

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;