/* Binary GCD algorithm in C
Source: http://en.wikipedia.org/wiki/Binary_GCD_algorithm
This code is licensed under the Creative Commons AttributionShareAlike License.
It is from the Wikipedia article "Counting sort" dated 20100117. */
/* The binary GCD algorithm, also known as Stein's algorithm, is an
algorithm that computes the greatest common divisor of two nonnegative
integers. It gains a measure of efficiency over the ancient Euclidean
algorithm by replacing divisions and multiplications with shifts, which
are cheaper when operating on the binary representation used by modern
computers. */
/* Following is an implementation of the algorithm in C, taking two
(nonnegative) integer arguments u and v. It first removes all common
factors of 2 using identity 2, then computes the GCD of the remaining
numbers using identities 3 and 4, and combines these to form the final
answer. */
typedef unsigned long long uint64;
uint64 gcd(uint64 u, uint64 v)
{
int shift;
/* GCD(0,x) := x */
if (u == 0  v == 0)
return u  v;
/* Let shift := lg K, where K is the greatest power of 2
dividing both u and v. */
for (shift = 0; ((u  v) & 1) == 0; ++shift) {
u >>= 1;
v >>= 1;
}
while ((u & 1) == 0)
u >>= 1;
/* From here on, u is always odd. */
do {
while ((v & 1) == 0) /* Loop X */
v >>= 1;
/* Now u and v are both odd, so diff(u, v) is even.
Let u = min(u, v), v = diff(u, v)/2. */
if (u < v) {
v = u;
} else {
uint64 diff = u  v;
u = v;
v = diff;
}
v >>= 1;
} while (v != 0);
return u << shift;
}
