matlab中的扩展算法实现

Question

我发现了以下扩展欧几里德算法的伪代码

我实现了以下算法

    function [x1,y1,d1]=extend_eucledian(a,b)
            if b==0
                x1=1;
                y1=0;
                d1=a;
                return;
            end

            [x1,y1,d1]=extend_eucledian(b,mod(a,b));


 x1=y1;
y1=x1-floor(a/b)*y1;
d1=d1;

        end

当我运行关注这个程序时，我得到了以下结果

[x1,y1,d1]=extend_eucledian(23,20)

x1 =

     0


y1 =

     0


d1 =

     1

我猜 [x1,y1,d1] 在迭代过程中没有改变它们的值，例如，我试过下面的代码

    function [x1,y1,d1]=extend_eucledian(a,b)
            if b==0
                x1=1;
                y1=0;
                d1=a;
                return;
            else
                 x1=y1;
y1=x1-floor(a/b)*y1;
d1=d1;
            end

            [x1,y1,d1]=extend_eucledian(b,mod(a,b));



        end

但是我得到了

>> [x1,y1,d1]=extend_eucledian(23,20)
Undefined function or variable 'y1'.

Error in extend_eucledian (line 8)
                 x1=y1;

我该如何解决这个问题？我哪里弄错了？

Answer 1

题中的错误是x1, y1, d1同时作为工作变量和输出变量。可以使用新的 tern [x, y d] 重写代码，输出值：

function [x y d]=eucledian_pairs(a,b)
%a>0,b>0
%d=gcd(a,b)  a*x+y*b=d
[x1,y1,d1]=extend_eucledian(a,b);

x=y1;
y=x1-floor(a/b)*y1;
d=d1;    

    function [x1,y1,d1]=extend_eucledian(a,b)
        if b==0
            x1=1;
            y1=0;
            d1=a;
            return;
        end
        [x1,y1,d1]=extend_eucledian(b,mod(a,b));                
    end    
end

执行此代码会得到所需的结果。

>> [x y d]=eucledian_pairs(20,25)

x =

     0


y =

     1


d =

     5

Answer 2

问题可以通过引入中间工作变量来解决，它将存储递归调用的结果：

function [x,y,d]=extended_euclid(a,b)
    if b==0
        x=1;
        y=0;
        d=a;
        return;
    end
    [x1,y1,d1]=extended_euclid(b,mod(a,b));  

    x=y1;
    y=x1-floor(a/b)*y1;
    d=d1;

end

此函数按预期工作：

>> [x, y, d] = extended_euclid(23,20)

x =    
     7

y =    
    -8

d =    
     1


>> [x, y, d] = extended_euclid(25,20)

x =    
     1    

y =    
    -1    

d =    
     5

matlab中的扩展算法实现

extended algorithm implementation in matlab

matlab

modular-arithmetic