二进制欧几里得算法进入无限循环

Question

我已经在matlab中实现了二进制欧几里得算法，这里是代码

 function d=EuclidBinary(a,b)
    if a==0
        d=b;
        return ;

    elseif b==0
        d=a;
        return;
    elseif mod(a,2)==0 && mod(b,2)==0
        d=2*EuclidBinary(a/2,b/2);
    elseif mod(a,2)==0 && mod(b,2)==1
             d=EuclidBinary(a/2,b);
         elseif mod(a,2)==1 && mod(b,2)==0
         d=EuclidBinary(a,b/2);
    else
         d=EuclidBinary(fix(abs(a-b)/2),b);




    end

然后我输入了以下数据

 a=27;
b=36;
d=EuclidBinary(a,b)

d =

     9

它工作正常，但是当我更改为以下数据时

a=36;
b=28;
d=EuclidBinary(a,b)
Out of memory. The likely cause is an infinite recursion within the program.

Error in EuclidBinary (line 16)
         d=EuclidBinary(fix(abs(a-b)/2),b);

我已经开始调试，如果我按照说明进行操作，那么我就会

d=2*EuclidBinary(a/2,b/2);第一次通话 (a=18,b=14) 第二次相同 d=2*EuclidBinary(a/2,b/2); (a=9,b=7)

对于第三种情况，我们有 a=1 b=7 通常程序会无限次重复这些值，我使用以下伪代码

请帮我解决这个问题

Answer 1

这个算法（您消息底部的打印屏幕）似乎有缺陷。让我们看看如果 a=1 和 b=7 会发生什么：

a=1,b=7 --> a=(6/2)=3, b=7 --> a=(4/2)=2, b=7 --> a=1, b=7.

所以问题不在您的代码中，而在您使用的算法中。它只是用这个输入进入无限循环。

我认为错误在第 4 步。请参阅 following link。在您的问题中，第 4 步在每种情况下都将 b 作为其第二个参数，而在我给您的 link 中，第二个参数由某些条件决定。另请注意，还有第 5 步。

Answer 2

您的算法有误。参见 Binary GCD Algorithm。最后一种情况 a 和 b 都是奇数，应该不同地处理：

function d=EuclidBinary(a,b)
if a==0
   d = b;
   return;       
elseif b==0
   d = a;
   return;
elseif mod(a, 2)==0 && mod(b, 2)==0     % Both a and b are even.
   d = 2*EuclidBinary(a/2, b/2);
elseif mod(a, 2)==0 && mod(b, 2)==1     % a is even
   d = EuclidBinary(a/2, b);
elseif mod(a, 2)==1 && mod(b, 2)==0     % b is even
   d = EuclidBinary(a, b/2);
else
   if (a>b)                           % both are a and b are odd  
      d = EuclidBinary((a-b)/2, b);     % <- b is the  second argument
   else
      d = EuclidBinary((b-a)/2, a);     % <- a is the  second argument
   end
end

二进制欧几里得算法进入无限循环

BInary Eucledian algorithms goes to infinite loop

matlab

infinite-loop

modular-arithmetic