What Is the Binary GCD (Stein’s) Algorithm?

The binary GCD algorithm, also known as Stein’s algorithm, is an efficient method for computing the greatest common divisor of two non-negative integers. Unlike the traditional Euclidean algorithm, which relies on division and modulo operations, Stein’s algorithm calculates the GCD using arithmetic shifts, subtractions, and bitwise operations. This article explains how Stein’s algorithm works and why its reliance on low-level binary primitives makes it substantially faster on modern computer hardware.

How Stein’s Algorithm Works

Published by Josef Stein in 1967, the binary GCD algorithm finds the GCD of two integers, \(u\) and \(v\), by applying four fundamental mathematical properties:

  1. Both numbers are even: \(\gcd(u, v) = 2 \cdot \gcd(u/2, v/2)\). The common factor of 2 is extracted.
  2. One number is even, the other is odd: If \(u\) is even and \(v\) is odd, \(\gcd(u, v) = \gcd(u/2, v)\). The factor of 2 does not divide \(v\), so it can be safely discarded from \(u\).
  3. Both numbers are odd: \(\gcd(u, v) = \gcd(|u - v|/2, \min(u, v))\). The difference of two odd numbers is even, allowing immediate division by 2 in the next step.
  4. Base cases: \(\gcd(0, v) = v\) and \(\gcd(u, 0) = u\).

The algorithm repeatedly strips out shared powers of two, reduces odd numbers via subtraction, and shifts out remaining factors of two until the base case is reached.

The Euclidean Algorithm vs. Stein’s Algorithm

The classical Euclidean algorithm computes the GCD using repeated division:

\[\gcd(a, b) = \gcd(b, a \bmod b)\]

While mathematically concise, the Euclidean algorithm requires an integer division or modulo operation at every iteration.

In contrast, Stein’s algorithm eliminates division entirely, substituting it with: * Right bit-shifts to divide by 2 * Bitwise AND operations to test whether a number is even or odd * Integer subtractions to reduce the larger number

Why Stein’s Algorithm Is Faster on Binary Hardware

Modern computer hardware operates natively in the binary number system (base 2). This architecture makes the operations in Stein’s algorithm significantly cheaper to execute than standard division:

1. Single-Cycle Bit-Shifts

In binary, dividing an integer by 2 is equivalent to shifting its bits one position to the right (x >> 1). CPUs can execute bit-shifts and bitwise tests (x & 1) in a single clock cycle.

2. High Cost of Hardware Division

Integer division (/) and modulo (%) are among the slowest arithmetic instructions on modern CPUs. While addition, subtraction, and shifts typically take 1 clock cycle, hardware division can take anywhere from 10 to 40+ clock cycles depending on the processor architecture. By replacing division with subtraction and shifting, Stein’s algorithm avoids this hardware bottleneck.

3. Acceleration via Count Trailing Zeros (CTZ)

Modern processors include specialized instructions, such as CTZ (Count Trailing Zeros) or CLZ (Count Leading Zeros), implemented in hardware. Stein’s algorithm can use a single CTZ instruction to count and strip all powers of two from a number at once via a multi-bit shift, rather than looping one bit at a time. This reduces the total number of loop iterations dramatically.

Summary

The binary GCD algorithm is an optimization designed specifically for digital hardware. By aligning the mathematical reduction steps with native binary operations—shifts, masking, and subtractions—Stein’s algorithm bypasses expensive division circuits, delivering superior performance for multi-precision arithmetic, cryptography, and computer algebra systems.