The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Although the algorithm in its contemporary form was first published by the Israeli physicist and programmer Josef Stein in 1967, it may have been known by the 2nd century BCE, in ancient China. Algorithm The algorithm reduces the problem of finding the GCD of two nonnegative numbers v and u by repeatedly applying these identities: gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(2u, 2v) = 2·gcd(u, v) gcd(2u, v) = gcd(u, v), if v is odd (2 is not a common divisor). Similarly, gcd(u, 2v) = gcd(u, v) if u is odd. gcd(u, v) = gcd(|u − v|, min(u, v)), if u and v are both odd. Implementation While the above description of the algorithm is mathematically-correct, performant software implementations typically differ from it in a few notable ways: eschewing trial division by 2 in favour of a single bitshift and the count trailing zeros primitive; this is functionally equivalent to repeatedly applying identity 3, but much faster; expressing the algorithm iteratively rather than recursively: the resulting implementation can be laid out to avoid repeated work, invoking identity 2 at the start and maintaining as invariant that both numbers are odd upon entering the loop, which only needs to implement identities 3 and 4; making the loop's body branch-free except for its exit condition (v == 0): in the example below, the exchange of u and v (ensuring u ≤ v) compiles down to conditional moves; hard-to-predict branches can have a large, negative impact on performance. Following is an implementation of the algorithm in Rust exemplifying those differences, adapted from uutils: pub fn gcd(mut u: u64, mut v: u64) -> u64 { use std::cmp::min; use std::mem::swap; // Base cases: gcd(n, 0) = gcd(0, n) = n if u == 0 { return v; } else if v == 0 { return u; } // Using identities 2 and 3: // gcd(2ⁱ u, 2ʲ v) = 2ᵏ gcd(u, v) with u, v odd and k = min(i, j) // 2ᵏ is the greatest power of two that divides both