Find the GCD of two numbers without using divison or mod operator?
12,238
Solution 1
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
Solution 2
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
Comments
-
jairaj almost 2 years
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 ??
-
amit over 11 yearsThis is basically a bitwise way to implement mod and divisions :|
-
Pascal Cuoq over 11 yearsThis is mind-blowing. How the heck did it get downvoted? (apart from the fact that until one carefully reads the cases “p and q odd”, it looks like it cannot possibly work, perhaps)
-
Pascal Cuoq over 11 years@H2CO3 This is what I would have been posting too. What we should have been posting is Bobby Dizzles's version below.
-
dbush over 3 yearsThe question specifically asked for an implementation that doesn't use division.
-
easymathematics over 3 yearsIf one like use a division function based on subtraction.