Binary GCD algorithm

The binary GCD algorithm relies on the fact that the GCD of two numbers is unchanged if both are even (factor out a common power of two), if one is even and the other odd (remove the even factor), or if both are odd (replace the larger by their difference). The algorithm repeatedly applies these rules until one number becomes zero, then multiplies the result by the accumulated power of two.¹

Formally, for non-negative integers a and b, the algorithm tracks a shift count k for common factors of two. It removes all factors of two from each number, then repeatedly subtracts the smaller from the larger, removing factors of two from the result after each subtraction. The final GCD is the remaining odd number shifted left by k bits. This approach avoids division entirely, making it faster than the Euclidean algorithm on hardware where division is slow.²

The algorithm was first described by Josef Stein in 1967 and published in the Journal of Computational Physics in 1971.³ It is sometimes called Stein's algorithm in honor of its discoverer. Although the Euclidean algorithm dates back to ancient Greece, the binary variant was developed specifically for the emerging digital computers of the mid-20th century, where bitwise operations were significantly faster than arithmetic division.

The algorithm's simplicity and efficiency made it a staple in early computer science curricula and in the design of cryptographic systems. It is also known as the "binary Euclidean algorithm" in some literature, though this name can be confused with other binary-based GCD methods. The algorithm's reliance on subtraction and bit shifts makes it particularly well-suited for hardware implementations and for use in embedded systems with limited arithmetic capabilities.⁴

The binary GCD algorithm has a worst-case time complexity of O(log n) bit operations, which is comparable to the Euclidean algorithm's O(log n) divisions, but with a much smaller constant factor on typical hardware. In practice, it is often 2–5 times faster than the Euclidean algorithm for large integers, especially when division is implemented in software.⁵

Several variants exist to improve performance further. The "extended binary GCD" algorithm also computes Bézout coefficients, which are essential for modular inverses in RSA and other cryptographic protocols. Another variant, the "left-shift binary GCD," processes bits from the most significant end, which can be advantageous in certain hardware designs. The algorithm is also used as a building block in more complex number-theoretic algorithms, such as the GCD of polynomials over finite fields.⁶

One lesser-known fact is that the binary GCD algorithm was independently discovered by several researchers in the 1960s, including a version by the mathematician Derrick Lehmer, though Stein's publication is the most widely cited.⁷ The algorithm also appears in the Hacker's Delight book by Henry S. Warren, which popularized it among software engineers.

Another edge case is that the algorithm handles zero inputs gracefully: the GCD of zero and any number is the number itself, and the algorithm's rules naturally produce this result. Additionally, the algorithm can be extended to negative integers by taking absolute values, and to more than two numbers by iterating pairwise. In some implementations, the algorithm is combined with lookup tables for small numbers to reduce the number of iterations, a technique known as "binary GCD with table lookup."⁸

Greatest common divisor

The largest positive integer that divides two or more integers without a remainder.

Bitwise operation

An operation that acts on the individual bits of a binary number, such as AND, OR, XOR, and bit shifts.

Euclidean algorithm

A classical method for computing the GCD by repeated division, dating back to ancient Greece.

Bézout coefficients

Integers x and y such that ax + by = gcd(a, b), used in modular arithmetic and cryptography.