public static long gcd()

in commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java [141:192]
31 lines of code
9 McCabe index (conditional complexity)

    public static long gcd(long p, long q) {
        // Perform the gcd algorithm on negative numbers, so that -2^63 does not
        // need to be handled separately
        long a = p > 0 ? -p : p;
        long b = q > 0 ? -q : q;

        long negatedGcd;
        if (a == 0) {
            negatedGcd = b;
        } else if (b == 0) {
            negatedGcd = a;
        } else {
            // Make "a" and "b" odd, keeping track of common power of 2.
            final int aTwos = Long.numberOfTrailingZeros(a);
            final int bTwos = Long.numberOfTrailingZeros(b);
            a >>= aTwos;
            b >>= bTwos;
            final int shift = Math.min(aTwos, bTwos);

            // "a" and "b" are negative and odd.
            // If a < b then "gdc(a, b)" is equal to "gcd(a - b, b)".
            // If a > b then "gcd(a, b)" is equal to "gcd(b - a, a)".
            // Hence, in the successive iterations:
            //  "a" becomes the negative absolute difference of the current values,
            //  "b" becomes that value of the two that is closer to zero.
            while (true) {
                final long delta = a - b;

                if (delta == 0) {
                    // This way of terminating the loop is intentionally different from the int gcd implementation.
                    // Benchmarking shows that testing for long inequality (a != b) is slow compared to
                    // testing the delta against zero. The same change on the int gcd reduces performance there,
                    // hence we have two variants of this loop.
                    break;
                }

                b = Math.max(a, b);
                a = delta > 0 ? -delta : delta;

                // Remove any power of 2 in "a" ("b" is guaranteed to be odd).
                a >>= Long.numberOfTrailingZeros(a);
            }

            // Recover the common power of 2.
            negatedGcd = a << shift;
        }
        if (negatedGcd == Long.MIN_VALUE) {
            throw new NumbersArithmeticException("overflow: gcd(%d, %d) is 2^63",
                    p, q);
        }
        return -negatedGcd;
    }