in commons-numbers-core/src/main/java/org/apache/commons/numbers/core/ArithmeticUtils.java [145:201]
public static long gcd(final long p, final long q) {
long u = p;
long v = q;
if (u == 0 || v == 0) {
if (u == Long.MIN_VALUE || v == Long.MIN_VALUE) {
throw new NumbersArithmeticException(OVERFLOW_GCD_MESSAGE_2_POWER_63,
p, q);
}
return Math.abs(u) + Math.abs(v);
}
// keep u and v negative, as negative integers range down to
// -2^63, while positive numbers can only be as large as 2^63-1
// (i.e. we can't necessarily negate a negative number without
// overflow)
/* assert u!=0 && v!=0; */
if (u > 0) {
u = -u;
} // make u negative
if (v > 0) {
v = -v;
} // make v negative
// B1. [Find power of 2]
int k = 0;
while ((u & 1) == 0 && (v & 1) == 0 && k < 63) { // while u and v are
// both even...
u /= 2;
v /= 2;
k++; // cast out twos.
}
if (k == 63) {
throw new NumbersArithmeticException(OVERFLOW_GCD_MESSAGE_2_POWER_63,
p, q);
}
// B2. Initialize: u and v have been divided by 2^k and at least
// one is odd.
long t = ((u & 1) == 1) ? v : -(u / 2)/* B3 */;
// t negative: u was odd, v may be even (t replaces v)
// t positive: u was even, v is odd (t replaces u)
do {
/* assert u<0 && v<0; */
// B4/B3: cast out twos from t.
while ((t & 1) == 0) { // while t is even..
t /= 2; // cast out twos
}
// B5 [reset max(u,v)]
if (t > 0) {
u = -t;
} else {
v = t;
}
// B6/B3. at this point both u and v should be odd.
t = (v - u) / 2;
// |u| larger: t positive (replace u)
// |v| larger: t negative (replace v)
} while (t != 0);
return -u * (1L << k); // gcd is u*2^k
}