1
\$\begingroup\$

If either a or b is 0 return the other number. If both even return gcd of a/2 and b/2. If either a or b is even divide it by 2 and return gcd of the pair. If a less than or equal to b, return the gcd of a, a-b else return gcd of b, a-b

private int gcd(int a, int b){
        if(a == 0) return b;
        if(b == 0) return a;
        boolean isAEven = (a & 1) == 0;
        boolean isBEven = (b & 1) == 0;
       // if a and b are divisible by 2
        if(isAEven && isBEven){
            return gcd( a >> 1,  b >> 1) << 1;
        }
        if(isAEven && !isBEven){
            return gcd( a >> 1, b);
        }
        if(!isAEven && isBEven){
            return gcd(a, b >> 1);
        }
        if(a <= b){
            return gcd(a, b-a);
        } else {
            return gcd(b, a-b);
        }
    }
\$\endgroup\$
  • \$\begingroup\$ You're using multiplication. \$\endgroup\$ – Eric Stein Mar 27 '18 at 0:58
  • \$\begingroup\$ @EricStein I tested his code, it seems to be working fine and giving correct answers (although it is quite slow). See on repl.it \$\endgroup\$ – Phrancis Mar 27 '18 at 1:23
  • \$\begingroup\$ @EricStein fixed it \$\endgroup\$ – saneGuy Mar 27 '18 at 2:08
  • \$\begingroup\$ @Phrancis The title said "without using multiplication". The code was using multiplication. \$\endgroup\$ – Eric Stein Mar 27 '18 at 2:10
  • \$\begingroup\$ @Phrancis fixed it now \$\endgroup\$ – saneGuy Mar 27 '18 at 2:11
1
\$\begingroup\$

The code in general looks decent. There are some minor things in coding style that could be improved.

I would rename isAEven to aIsEven or aEven. A variable is a state, not a question.

The method in itself doesn't rely on any state of some object. It's a utility function. It would make more sense if it were static instead. If you plan to provide other similar utility functions you could write a specific class to group those. Similar to the Math class already available in java.

In this block:

    if(isAEven && isBEven){
        return gcd( a >> 1,  b >> 1) << 1;
    }
    if(isAEven && !isBEven){
        return gcd( a >> 1, b);
    }
    if(!isAEven && isBEven){
        return gcd(a, b >> 1);
    }

the checks for !isXEven are redundant. After the first if, you know that not both are even. Whether or not to remove this is your choice on which is more readable. Alternatively you could write it as:

    if(isAEven && isBEven){
        return gcd( a >> 1,  b >> 1) << 1;
    } else if(isAEven){
        return gcd( a >> 1, b);
    } else if(isBEven){
        return gcd(a, b >> 1);
    }

I added the else to make it explicit that these 3 actually belong together. Changing the order isn't allowed anymore after removing the !... check.


About the actual algorithm. it looks slightly different from what I've seen before. Doing a little searching on the internet I found out it's almost the same as this Binary GCD algorithm.

You're only missing 2 optimisations.

The first one is the obvious if(a == b) return a. When both are equal you don't need to calculate anything else. The biggest difference can be seen if a = b = 1<<30 (the biggest integer power of 2) where your algorithm takes about 32 recursive steps.

The other optimisation is a bit less obvious. The last 2 recursive calls in the code can also use a bitshift:

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

Because at that point we know a (or b) is odd and b-a (or a-b) is even. We can skip a cycle to bitshift the new b immediatly.

Side note: you don't really need all the bitshifting if you're not interested in micro-optimisations for speed. The simplified version also works fast as is:

private static int gcd(int a, int b) {
    if (a == b) return a;
    if (a == 0) return b;
    if (b == 0) return a;

    if (a <= b) {
        return gcd(a, b - a);
    } else {
        return gcd(b, a - b);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.