algorithm - Maple 中的扩展欧几里得算法

Question

这是我在 Maple 中扩展欧几里德算法的代码，它应该返回整数 l , 多项式 pi,ri,si,ti对于 0<=i<=l+1 .和多项式qi对于 1<=i<=l这样 si(f)+ti(g) = ri和 sl(f)+tl(g)=rl=GCD(f,g) .

问题是，我总是被零除。它还评估 pi = lcoeff(ri-1 - qiri)每次都为零。即使我删除它它仍然说有零的除法，它必须来自 qi:=quo(ri-1,ri, x);但是我不知道为什么考虑循环的要求是 r[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+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;