Explain how coprime check works

Question

Every time I use the Euclid method for checking if two numbers are co-prime. But there is one solution which has used this code to check for co-primeness, and the time taken by this was much faster than the Euclid method: (source)

private static boolean isCoprime(long u, long v) {
    if (((u | v) & 1) == 0)
        return false;

    while ((u & 1) == 0)
        u >>= 1;
    if (u == 1)
        return true;

    do {
        while ((v & 1) == 0)
            v >>= 1;
        if (v == 1)
            return true;

        if (u > v) {
            long t = v;
            v = u;
            u = t;
        }
        v -= u;
    } while (v != 0);

    return false;
}

I'm unable to understand how is this working. (I do understand bitwise operations.) For example, what do these lines mean...

if (((u | v) & 1) == 0)
    return false;

Why simply return false? Also there are other lines which I'm not able to understand what is happening. If any one of you could you just give me some walkthrough it will be of much help.

Answer 1

The code you posted is a modification of the binary GCD algorithm. Here is my annotated commentary:

private static boolean isCoprime(long u, long v) {
    // If both numbers are even, then they are not coprime.
    if (((u | v) & 1) == 0) return false;

    // Now at least one number is odd. Eliminate all the factors of 2 from u.
    while ((u & 1) == 0) u >>= 1;

    // One is coprime with everything else by definition.
    if (u == 1) return true;

    do {
        // Eliminate all the factors of 2 from v, because we know that u and v do not have any 2's in common.
        while ((v & 1) == 0) v >>= 1;

        // One is coprime with everything else by definition.
        if (v == 1) return true;

        // Swap if necessary to ensure that v >= u.
        if (u > v) {
            long t = v;
            v = u;
            u = t;
        }

        // We know that GCD(u, v) = GCD(u, v - u).
        v -= u;
    } while (v != 0);

    // When we reach here, we have v = 0 and GCD(u, v) = current value of u, which is greater than 1.
    return false;
}