Search code examples
matlabinfinite-loopmodular-arithmetic

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

Solution

  • 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.