CODEWITHSUNDEEP
calgorithmnumbers
jairaj
jairaj

Reputation: 1869

Find the GCD of two numbers without using divison or mod operator?

I want to find GCD of two numbers but without using division or mod operator. one obvious way would be to write own mod function like this:

enter code here
int mod(int a, int b)
{
   while(a>b)
       a-=b;

return a;
}

and then use this function in the euclid algorithm. Any other way ??

Upvotes: 2

Views: 14116

Answers (4)

easymathematics
easymathematics

Reputation: 1

A more or less direct way is the following code, which is derived from Pick's theorem:

int gcd(int a, int b)
{

     if( a < 0)
     {
         a = -a;
     }

     if( b < 0)
     {
         b = -b;
     }

     if( a == b)
     {
          return a;
     }

     //swap the values to make the upper bound in the next loop minimal
     if( a > b)
     {
        int swap = a;
        a = b;
        b = swap;
     }
     

     int temp=0;

     for(int i=1; i<=a; i++)
     {
          temp += math.floor(b*i/a);
     }

     return (a*b + b - a + temp)/2;
}

Upvotes: -1

Sunil Bojanapally
Sunil Bojanapally

Reputation: 12658

Recursive GCD computing using subtraction:

int GCD(int a, int b)
{
    int gcd = 0;
    if(a < 0)
    {
        a = -a;
    }
    if(b < 0)
    {
        b = -b;
    }
    if (a == b)
    {
        gcd = a;
        return gcd;
    }
    else if (a > b)
    {
        return GCD(a-b,b);
    }
    else
    {
        return GCD(a,b-a);
    }
}

Source: link

Upvotes: 0

amit
amit

Reputation: 178481

You can use the substraction based version of euclidean algorithm up front:

function gcd(a, b)
    if a = 0
       return b
    while b ≠ 0
        if a > b
           a := a − b
        else
           b := b − a
    return a

Upvotes: 14

Bobb Dizzles
Bobb Dizzles

Reputation: 539

What you are looking for is the Binary GCD algorithm: 

public class BinaryGCD {

    public static int gcd(int p, int q) {
        if (q == 0) return p;
        if (p == 0) return q;

        // p and q even
        if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;

        // p is even, q is odd
        else if ((p & 1) == 0) return gcd(p >> 1, q);

        // p is odd, q is even
        else if ((q & 1) == 0) return gcd(p, q >> 1);

        // p and q odd, p >= q
        else if (p >= q) return gcd((p-q) >> 1, q);

        // p and q odd, p < q
        else return gcd(p, (q-p) >> 1);
    }

    public static void main(String[] args) {
        int p = Integer.parseInt(args[0]);
        int q = Integer.parseInt(args[1]);
        System.out.println("gcd(" + p + ", " + q + ") = " + gcd(p, q));
    }
}

Source: http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Upvotes: 11

Related Questions