The algorithm reduces the problem of finding the GCD by repeatedly applying these identities:
gcd = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd = u.
gcd = 2·gcd
gcd = gcd, if v is odd. Similarly, gcd = gcd if u is odd.
gcd = gcd, if u and v are both odd.
For word-sized integers, the algorithm requires a number of machine operations on the order of log. Asymptotically, the algorithm requires O worst-case time, where n is the number of bits in the larger of the two numbers: although each step reduces at least one of the operands by at least a factor of 2, the subtract and shift operations take linear time. An extended binary GCD, analogous to the extended Euclidean algorithm, is given by Knuth along with pointers to other versions.
Following is a recursive implementation of the algorithm in C. The implementation is similar to the description of the algorithm given above. It uses two arguments u and v. All but one of the recursive calls are tail recursive. unsigned int gcd
Iterative version in C
Following is an implementation of the algorithm in C, taking two 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. unsigned int gcd
Efficiency
Akhavi and Vallée proved that binary GCD is about 60% more efficient on average, in terms of the number of bit operations, than the Euclidean algorithm. This algorithm achieves the same asymptotic complexity as the Euclidean algorithm, though neither is the fastest for arbitrary-precision arithmetic, as they both take quadratic time. Instead, recursive methods that combine ideas from the binary GCD algorithm with the Schönhage–Strassen algorithm for fast integer multiplication can find GCDs in near-linear time.
Historical description
An algorithm for computing the GCD of two numbers was described in the ancient Chinese mathematics book The Nine Chapters on the Mathematical Art. The original algorithm was used to reduce a fraction. The description reads: "If possible halve it; otherwise, take the denominator and the numerator, subtract the lesser from the greater, and do that alternately to make them the same. Reduce by the same number." This description looks like a normal Euclidean algorithm, but there is ambiguity in the phrase "if possible halve it". The traditional interpretation is that this only applies when 'both' numbers are even, implying the algorithm is just slightly inferior to the Euclidean algorithm. But the phrase may mean dividing by 2 should 'either' of the numbers become even, in which case it is the binary GCD algorithm.
