/* binary GCD alg. Based on following facts. If N and M are even, then gcd(N,M) = 2 * gcd (N/2, M/2) If N even and M odd, then gcd(N,M) = gcd(N/2, M) If N,M odd, then |N-M|<max(N,M) thus guaranteeing that we can use gcd(N,M) = gcd(N-M,M) to reduce. fact: a&1 is 1 iff a is odd. Mult. and Div. by 2 more efficiently implemented as shift-left 1 and shift-right 1 resp. */ long gcd( long a, long b) { int t; if (a < 0) a = -a; if (!b) return a; if (b < 0) b = -b; if (!a) return b; t = 0; while (! ((a|b) & 1)) {a >>= 1; b >>= 1; ++t;} while (! (a&1)) a >>= 1; while (! (b&1)) b >>= 1; while (a != b) { if (a > b) { a -= b; do {a >>= 1;} while (! (a&1)); } else { b -= a; do {b >>= 1;} while (! (b&1)); } } return(a<<t); }