BinaryGCD.java

Below is the syntax highlighted version of BinaryGCD.java from §2.3 Recursion.

/******************************************************************************
 *  Compilation:  javac BinaryGCD.java
 *  Execution:    java BinaryGCD p q
 *
 *  Reads two commandline parameters p and q and computes the greatest
 *  common divisor of p and q using 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]);
        StdOut.println("gcd(" + p + ", " + q + ") = " + gcd(p, q));
    }
}