CODEWITHSUNDEEP
matlabinfinite-loopmodular-arithmetic
user466534
user466534

Reputation:

BInary Eucledian algorithms goes to infinite loop

i have implemented binary eucledian algorithm in matlab, here is code

 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

then i have entered following data

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

d =

     9

it works fine, but when i have changed to the following data

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);

i have started debugging and if i follow instructions, then i will have

d=2*EuclidBinary(a/2,b/2); for first call (a=18,b=14) for the second the same d=2*EuclidBinary(a/2,b/2); (a=9,b=7)

for the third case we have a=1 b=7 and in generally program repeats those values for infinite times,i use following pseudo code enter image description here

please help me to fix this

Upvotes: 0

Views: 57

Answers (2)

Jørgen
Jørgen

Reputation: 863

There is an error in your algorithm. See Binary GCD Algorithm. The last case where a and b are both odd, should be handled differently:

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

Upvotes: 1

Miriam Farber
Miriam Farber

Reputation: 19634

This algorithm (the print screen from the bottom of your message) seems to have flaws. Let's see what happens if a=1 and b=7:

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

So the problem is not in your code, but in the algorithm that you used. It just goes to an infinite loop with this input.

I think the mistake is in step 4. See the following link. In your question, step 4 has b as its second parameter in every case, while in the link that I gave you the second parameter is determined by certain conditions. Also notice that there is step 5.

Upvotes: 2

Related Questions