it provides the Bézout coefficients in addition to the GCD, i.e. integers a and b such that a·u + b·v = gcd(u, v). In the case of large integers, the best asymptotic complexity is O(log n M(n)), with M(n) the cost of n-bit multiplication; this is near-linear, and vastly smaller than the O(n2) of the binary GCD algorithm, though concrete implementations only outperform older algorithms for numbers larger than about 64 kilobits (i.e. greater than 8×1019265). This is achieved by extending the binary GCD algorithm using ideas from the Schönhage–Strassen algorithm for fast integer multiplication. The binary GCD algorithm has also been extended to domains other than natural numbers, such as Gaussian integers, Eisenstein integers, quadratic rings, and integer rings of number fields. Historical description An algorithm for computing the GCD of two numbers was known in ancient China, under the Han dynasty, as a method to reduce fractions: The phrase "if possible halve it" is ambiguous, if this applies when either of the numbers become even, the algorithm is the binary GCD algorithm; if this only applies when both numbers are even, the algorithm is similar to the Euclidean algorithm. See also Euclidean algorithm Extended Euclidean algorithm Least common multiple References Further reading Covers the extended binary GCD, and a probabilistic analysis of the algorithm. Covers a variety of topic, 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. External links NIST Dictionary of Algorithms and Data Structures: binary GCD algorithm Cut-the-Knot: Binary Euclid's Algorithm at cut-the-knot Analysis of the Binary Euclidean Algorithm (1976), a paper by Richard P. Brent, including a variant using left shifts Number theoretic algorithms Articles with example C code