Binary GCD algorithm
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 physicist and programmer Josef Stein in 1967,[3] it was known by the 2nd century BCE, in ancient China.
[4] The algorithm finds the GCD of two nonnegative numbers
by repeatedly applying these identities: As GCD is commutative (
While the above description of the algorithm is mathematically correct, performant software implementations typically differ from it in a few notable ways: The following is an implementation of the algorithm in Rust exemplifying those differences, adapted from uutils: Note: The implementation above accepts unsigned (non-negative) integers; given that
, the signed case can be handled as follows: Asymptotically, the algorithm requires
For arbitrarily large numbers, the asymptotic complexity of this algorithm is
,[8] as each arithmetic operation (subtract and shift) involves a linear number of machine operations (one per word in the numbers' binary representation).
If the numbers can be represented in the machine's memory, i.e. each number's size can be represented by a single machine word, this bound is reduced to:
This is the same as for the Euclidean algorithm, though a more precise analysis by Akhavi and Vallée proved that binary GCD uses about 60% fewer bit operations.
[9] The binary GCD algorithm can be extended in several ways, either to output additional information, deal with arbitrarily large integers more efficiently, or to compute GCDs in domains other than the integers.
The extended binary GCD algorithm, analogous to the extended Euclidean algorithm, fits in the first kind of extension, as it provides the Bézout coefficients in addition to the GCD: integers
[10][11][12] In the case of large integers, the best asymptotic complexity is
-bit multiplication; this is near-linear and vastly smaller than the binary GCD algorithm's
, though concrete implementations only outperform older algorithms for numbers larger than about 64 kilobits (i.e. greater than 8×1019265).
[13] The binary GCD algorithm has also been extended to domains other than natural numbers, such as Gaussian integers,[14] Eisenstein integers,[15] quadratic rings,[16][17] and integer rings of number fields.
[18] An algorithm for computing the GCD of two numbers was known in ancient China, under the Han dynasty, as a method to reduce fractions: 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.The phrase "if possible halve it" is ambiguous,[4] Covers the extended binary GCD, and a probabilistic analysis of the algorithm.
Covers a variety of topics, including the extended binary GCD algorithm which outputs Bézout coefficients, efficient handling of multi-precision integers using a variant of Lehmer's GCD algorithm, and the relationship between GCD and continued fraction expansions of real numbers.
An analysis of the algorithm in the average case, through the lens of functional analysis: the algorithms' main parameters are cast as a dynamical system, and their average value is related to the invariant measure of the system's transfer operator.
