How Stein’s Binary GCD Algorithm Works

Stein’s algorithm, also known as the binary GCD algorithm, computes the greatest common divisor (GCD) of two non-negative integers by replacing traditional division and modulo operations with bitwise right shifts, parity checks, and subtractions. While the classical Euclidean algorithm relies on integer division—an operation that requires multiple clock cycles on modern computer architectures—Stein’s algorithm operates natively in the binary number system. By using low-cost binary shifts (division by two) and subtraction, it significantly improves execution speed on digital processors.

The Problem with Euclidean Division

The standard Euclidean algorithm calculates the GCD using repeated division:

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

In binary hardware, calculating \(a \pmod b\) requires integer division circuitry, which is complex and slow compared to basic logic operations. Stein’s algorithm avoids division entirely by exploiting the algebraic properties of greatest common divisors in base-2 representation.

The Algebraic Rules of Stein’s Algorithm

Stein’s algorithm calculates \(\gcd(u, v)\) iteratively or recursively based on the parity (even or odd state) of the two integers:

  1. Both numbers are even (\(u\) is even, \(v\) is even): If both \(u\) and \(v\) are divisible by 2, then 2 is a common factor. \[\gcd(u, v) = 2 \cdot \gcd(u / 2, v / 2)\] In binary, \(u / 2\) and \(v / 2\) are calculated instantly using an arithmetic right shift: u >> 1 and v >> 1. The common factor of 2 is stored to multiply the final result later.

  2. One number is even, one is odd (\(u\) is even, \(v\) is odd): Because \(v\) is odd, 2 cannot be a common divisor of both numbers. The factor of 2 in \(u\) can be discarded without changing the GCD: \[\gcd(u, v) = \gcd(u / 2, v)\] The algorithm applies an arithmetic right shift to the even number: u = u >> 1.

  3. Both numbers are odd (\(u\) is odd, \(v\) is odd): When neither number has a factor of 2, the algorithm subtracts the smaller number from the larger number (assume \(u \ge v\)): \[\gcd(u, v) = \gcd(u - v, v)\] Since the difference between any two odd numbers is always an even number, \((u - v)\) is guaranteed to be even. In the very next iteration, this new even value can be reduced using arithmetic right shifts.

Step-by-Step Execution Model

To compute the GCD of \(u\) and \(v\):

  1. Extract Common Factors of Two: Count how many times both \(u\) and \(v\) can be simultaneously right-shifted. Let this count be \(k\). Shift both numbers right until at least one is odd.
  2. Remove Remaining Factors of Two: Shift whichever number is even to the right until both \(u\) and \(v\) are odd.
  3. Subtract and Shift Loop:
    • Ensure \(u \ge v\) (swap if necessary).
    • Set \(u = u - v\).
    • If \(u = 0\), the algorithm terminates, returning \(v \cdot 2^k\) (which is \(v \text{ \textless\textless } k\)).
    • Since \(u\) is now even, apply arithmetic right shifts (u = u >> 1) until \(u\) becomes odd again.
    • Repeat the loop.

Why This Approach Is Faster in Binary Hardware