u and v let i = u.trailing_zeros(); u >>= i; let j = v.trailing_zeros(); v >>= j; let k = min(i, j); loop { /// u and v are odd at the start of the loop debug_assert!(u % 2 == 1, "u = {} is even", u); debug_assert!(v % 2 == 1, "v = {} is even", v); // Swap if necessary so u <= v if u > v { swap(&mut u, &mut v); } /// u and v are still both odd after (potentially) swapping // Using identity 4 (gcd(u, v) = gcd(|v-u|, min(u, v)) v -= u; /// v is now even, but u is unchanged (and odd) // Identity 1: gcd(u, 0) = u // The shift by k is necessary to add back the 2ᵏ factor that was removed before the loop if v == 0 { return u << k; } // Identity 3: gcd(u, 2ʲ v) = gcd(u, v) (u is known to be odd) v >>= v.trailing_zeros(); /// v is now odd again } } Complexity The algorithm requires O(n) steps, where n is the number of bits in the larger of the two numbers, as every 2 steps reduce at least one of the operands by at least a factor of 2. Each step involves only a few arithmetic operations (O(1) with a small constant); when working with word-sized numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of n, i.e. log₂(max(u, v)). For arbitrary numbers, the asymptotic complexity of this algorithm is O(n2), as each arithmetic operation (subtract and shift) on arbitrary-sized integers involves a linear number of machine operations (one per word in the numbers' binary representation). This bound is reduced to O(n² / log₂ n) when assuming that the (input) numbers can be represented in the (abstract) machine's memory, i.e. the machine's words can represent each number's size. This is the same as for the Euclidean algorithm, though a more precise analysis by Akhavi and Vallée proved that binary GCD uses about 60% fewer bit operations. Extensions The binary GCD algorithm can be extended in several ways, either to output additional information, deal with arbitrarily-large integers more efficiently, or to compute GCDs in domains other than the integers. The extended binary GCD algorithm, analogous to the extended Euclidean algorithm, fits in the first kind of extension, as