# Binary GCD algorithm > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Binary_GCD_algorithm > Markdown URL: https://mediated.wiki/source/Binary_GCD_algorithm.md > Source: https://en.wikipedia.org/wiki/Binary_GCD_algorithm > Source revision: 1351092241 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Algorithm for computing the greatest common divisor Visualisation of using the binary GCD algorithm to find the greatest common divisor (GCD) of 36 and 24. Thus, the GCD is 22 × 3 = 12. The **binary GCD algorithm**, also known as **Stein's algorithm** or the **binary Euclidean algorithm**,[1][2] is an algorithm that computes the [greatest common divisor](/source/Greatest_common_divisor) (GCD) of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional [Euclidean algorithm](/source/Euclidean_algorithm); it replaces division with [arithmetic shifts](/source/Arithmetic_shift), 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] ## Algorithm The algorithm finds the GCD of two nonnegative numbers u {\displaystyle u} and v {\displaystyle v} by repeatedly applying these identities: 1. gcd ( u , 0 ) = u {\displaystyle \gcd(u,0)=u} : everything divides zero, and u {\displaystyle u} is the largest number that divides u {\displaystyle u} . 1. gcd ( 2 u , 2 v ) = 2 ⋅ gcd ( u , v ) {\displaystyle \gcd(2u,2v)=2\cdot \gcd(u,v)} : 2 {\displaystyle 2} is a common divisor. 1. gcd ( u , 2 v ) = gcd ( u , v ) {\displaystyle \gcd(u,2v)=\gcd(u,v)} if u {\displaystyle u} is odd: 2 {\displaystyle 2} is then not a common divisor. 1. gcd ( u , v ) = gcd ( u , v − u ) {\displaystyle \gcd(u,v)=\gcd(u,v-u)} if u , v {\displaystyle u,v} odd and u ≤ v {\displaystyle u\leq v} . As GCD is commutative ( gcd ( u , v ) = gcd ( v , u ) {\displaystyle \gcd(u,v)=\gcd(v,u)} ), those identities still apply if the operands are swapped: gcd ( 0 , v ) = v {\displaystyle \gcd(0,v)=v} , gcd ( 2 u , v ) = gcd ( u , v ) {\displaystyle \gcd(2u,v)=\gcd(u,v)} if v {\displaystyle v} is odd, etc. ## Implementation While the above description of the algorithm is mathematically correct, the binary GCD algorithm performs more loop iterations that the Euclidean one, so it only offers a performance advantage if those iterations are substantially faster. Performant software implementations typically differ from it in a few notable ways: - eschewing repeated [trial division](/source/Trial_division) by 2 {\displaystyle 2} in favour of the [count trailing zeros](/source/Count_trailing_zeros) primitive and a single [bit shift](/source/Bit_shift), which is functionally equivalent to repeatedly applying identity 3, but much faster; - expressing the algorithm [iteratively](/source/Iteration#Computing) rather than [recursively](/source/Recursion_(computer_science)): 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; and - making the loop's body [branch-free](/source/Branch_(computer_science)#Branch-free_code) except for its exit condition v == 0: [unpredictable branches](/source/Branch_predictor) can have a large, negative impact on performance.[5][6] The following is an implementation of the algorithm in [C](/source/C_(programming_language)). // Count trailing zeros. This is a pedagogical example only; // for efficiency use __builtin_ctzll() or similar. static int ctz(uint64_t n) { int s = 0, t; while ((t = n & 15) == 0) { n >>= 4; s += 4; } return s + ((0x12131210 >> 2*t) & 3); } uint64_t gcd(uint64_t u, uint64_t v) { if (!u || !v) return u | v; // Identity #1 int shift = ctz(u | v); u >>= ctz(u); uint64_t min, max; while (v) { v >>= ctz(v); // Identity #3 min = (u < v) ? u : v; // Identity #4 max = (u > v) ? u : v; u = min; v = max - min; } return u << shift; // Identity #2 } The following is an implementation of the algorithm in [Rust](/source/Rust_(programming_language)) exemplifying those differences, adapted from [*uutils*](https://github.com/uutils/coreutils/blob/31087e821dc81dfbe4ed97980ae1faa19cbb3250/src/uu/factor/src/numeric/gcd.rs). The conditional exchange of u {\displaystyle u} and v {\displaystyle v} (ensuring u ≤ v {\displaystyle u\leq v} ) compiles down to [conditional moves](/source/Conditional_moves);[7]: pub fn gcd(mut u: u64, mut v: u64) -> u64 { // 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 2ⁱ u and 2ʲ v let i = u.trailing_zeros(); u >>= i; let j = v.trailing_zeros(); v >>= j; let k = i.min(j); loop { // u and v are odd at the start of the loop debug_assert!(u % 2 == 1, "u = {} should be odd", u); debug_assert!(v % 2 == 1, "v = {} should be odd", v); // Swap if necessary so u ≤ v if u > v { (u, v) = (v, u); } // Identity 4: gcd(u, v) = gcd(u, v-u) as u ≤ v and u, v are both odd v -= u; // v is now even if v == 0 { // Identity 1: gcd(u, 0) = u // The shift by k is necessary to add back the 2ᵏ factor that was removed before the loop return u << k; } // Identity 3: gcd(u, 2ʲ v) = gcd(u, v) as u is odd v >>= v.trailing_zeros(); } } **Note**: The implementation above accepts *unsigned* (non-negative) integers; given that gcd ( u , v ) = gcd ( ± u , ± v ) {\displaystyle \gcd(u,v)=\gcd(\pm {}u,\pm {}v)} , the signed case can be handled as follows: /// Computes the GCD of two signed 64-bit integers /// The result is unsigned and not always representable as i64: gcd(i64::MIN, i64::MIN) == 1 << 63 pub fn signed_gcd(u: i64, v: i64) -> u64 { gcd(u.unsigned_abs(), v.unsigned_abs()) } ## Complexity [Asymptotically](/source/Big_O_notation), the algorithm requires O ( n ) {\displaystyle O(n)} steps, where n {\displaystyle n} is the number of bits in the larger of the two numbers, as every two steps reduce at least one of the operands by at least a factor of 2 {\displaystyle 2} . Each step involves only a few arithmetic operations ( O ( 1 ) {\displaystyle O(1)} with a small constant); when working with [word-sized](/source/Word_(computer_architecture)) numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of n {\displaystyle n} , i.e. log 2 ⁡ ( max ( u , v ) ) {\displaystyle \log _{2}(\max(u,v))} . For arbitrarily large numbers, the [asymptotic complexity](/source/Asymptotic_notation) of this algorithm is O ( n 2 ) {\displaystyle O(n^{2})} ,[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: O ( n 2 log 2 ⁡ n ) {\displaystyle O\left({\frac {n^{2}}{\log _{2}n}}\right)} 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] ## Extensions The binary GCD algorithm can be extended in several ways, either to output additional information, deal with [arbitrarily large integers](/source/Arbitrary-precision_arithmetic) more efficiently, or to compute GCDs in domains other than the integers. The *extended binary GCD* algorithm, analogous to the [extended Euclidean algorithm](/source/Extended_Euclidean_algorithm), fits in the first kind of extension, as it provides the [Bézout coefficients](/source/B%C3%A9zout_coefficients) in addition to the GCD: integers a {\displaystyle a} and b {\displaystyle b} such that a ⋅ u + b ⋅ v = gcd ( u , v ) {\displaystyle a\cdot {}u+b\cdot {}v=\gcd(u,v)} .[10][11][12] In the case of large integers, the best asymptotic complexity is O ( M ( n ) log ⁡ n ) {\displaystyle O(M(n)\log n)} , with M ( n ) {\displaystyle M(n)} the cost of n {\displaystyle n} -bit multiplication; this is near-linear and vastly smaller than the binary GCD algorithm's O ( n 2 ) {\displaystyle O(n^{2})} , 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](/source/Sch%C3%B6nhage%E2%80%93Strassen_algorithm) for fast integer multiplication.[13] The binary GCD algorithm has also been extended to domains other than natural numbers, such as [Gaussian integers](/source/Gaussian_integers),[14] [Eisenstein integers](/source/Eisenstein_integers),[15] quadratic rings,[16][17] and [integer rings](/source/Ring_of_integers) of [number fields](/source/Number_fields).[18] ## Historical description An algorithm for computing the GCD of two numbers was known in ancient China, under the [Han dynasty](/source/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. — Fangtian – Land surveying, *[The Nine Chapters on the Mathematical Art](/source/The_Nine_Chapters_on_the_Mathematical_Art)* The phrase "if possible halve it" is ambiguous,[4] - 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](/source/Euclidean_algorithm). ## See also - [Computer programming portal](https://en.wikipedia.org/wiki/Portal:Computer_programming) - [Euclidean algorithm](/source/Euclidean_algorithm) - [Extended Euclidean algorithm](/source/Extended_Euclidean_algorithm) - [Least common multiple](/source/Least_common_multiple) ## References 1. **[^](#cite_ref-brenta_1-0)** [Brent, Richard P.](/source/Richard_P._Brent) (13–15 September 1999). [*Twenty years' analysis of the Binary Euclidean Algorithm*](https://wwwmaths.anu.edu.au/~brent/pub/pub183.html). 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare. Oxford. 1. **[^](#cite_ref-brentb_2-0)** [Brent, Richard P.](/source/Richard_P._Brent) (November 1999). [*Further analysis of the Binary Euclidean algorithm*](https://www.cs.ox.ac.uk/techreports/oucl/tr-7-99.html) (Technical report). Oxford University Computing Laboratory. [arXiv](/source/ArXiv_(identifier)):[1303.2772](https://arxiv.org/abs/1303.2772). PRG TR-7-99. 1. **[^](#cite_ref-Stein_3-0)** Stein, J. (February 1967), "Computational problems associated with Racah algebra", *Journal of Computational Physics*, **1** (3): 397–405, [Bibcode](/source/Bibcode_(identifier)):[1967JCoPh...1..397S](https://ui.adsabs.harvard.edu/abs/1967JCoPh...1..397S), [doi](/source/Doi_(identifier)):[10.1016/0021-9991(67)90047-2](https://doi.org/10.1016%2F0021-9991%2867%2990047-2), [ISSN](/source/ISSN_(identifier)) [0021-9991](https://search.worldcat.org/issn/0021-9991) 1. ^ [***a***](#cite_ref-Knuth98_4-0) [***b***](#cite_ref-Knuth98_4-1) [Knuth, Donald](/source/Donald_Knuth) (1998), *Seminumerical Algorithms*, [The Art of Computer Programming](/source/The_Art_of_Computer_Programming), vol. 2 (3rd ed.), Addison-Wesley, [ISBN](/source/ISBN_(identifier)) [978-0-201-89684-8](https://en.wikipedia.org/wiki/Special:BookSources/978-0-201-89684-8) 1. **[^](#cite_ref-intel_5-0)** Kapoor, Rajiv (21 February 2009). ["Avoiding the Cost of Branch Misprediction"](https://software.intel.com/content/www/us/en/develop/articles/avoiding-the-cost-of-branch-misprediction.html). *Intel Developer Zone*. 1. **[^](#cite_ref-lemire_6-0)** Lemire, Daniel (15 October 2019). ["Mispredicted branches can multiply your running times"](https://lemire.me/blog/2019/10/15/mispredicted-branches-can-multiply-your-running-times/). 1. **[^](#cite_ref-rust_disassembly_7-0)** Godbolt, Matt. ["Compiler Explorer"](https://rust.godbolt.org/z/56jva3KPn). Retrieved 4 February 2024. 1. **[^](#cite_ref-gmplib_8-0)** ["GNU MP 6.1.2: Binary GCD"](https://gmplib.org/manual/Binary-GCD.html). 1. **[^](#cite_ref-bit-complexity_9-0)** Akhavi, Ali; Vallée, Brigitte (2000), ["Average Bit-Complexity of Euclidean Algorithms"](https://vallee.users.greyc.fr/Publications/icalp8-2000.ps), *Proceedings ICALP'00, Lecture Notes Computer Science 1853*: 373–387, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.42.7616](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.7616) 1. **[^](#cite_ref-egcd-knuth_10-0)** [Knuth 1998](#CITEREFKnuth1998), p. 646, answer to exercise 39 of section 4.5.2 1. **[^](#cite_ref-egcd-applied-crypto_11-0)** Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). ["§14.4 Greatest Common Divisor Algorithms"](https://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=17) (PDF). [*Handbook of Applied Cryptography*](http://cacr.uwaterloo.ca/hac/). CRC Press. pp. 606–610. [ISBN](/source/ISBN_(identifier)) [0-8493-8523-7](https://en.wikipedia.org/wiki/Special:BookSources/0-8493-8523-7). Retrieved 9 September 2017. 1. **[^](#cite_ref-egcd-cohen_12-0)** [Cohen, Henri](/source/Henri_Cohen_(number_theorist)) (1993). "Chapter 1 : Fundamental Number-Theoretic Algorithms". [*A Course In Computational Algebraic Number Theory*](https://books.google.com/books?id=hXGr-9l1DXcC). [Graduate Texts in Mathematics](/source/Graduate_Texts_in_Mathematics). Vol. 138. [Springer-Verlag](/source/Springer-Verlag). pp. 17–18. [ISBN](/source/ISBN_(identifier)) [0-387-55640-0](https://en.wikipedia.org/wiki/Special:BookSources/0-387-55640-0). 1. **[^](#cite_ref-stehlé-zimmermann_13-0)** Stehlé, Damien; [Zimmermann, Paul](/source/Paul_Zimmermann_(mathematician)) (2004), ["A binary recursive gcd algorithm"](https://hal.archives-ouvertes.fr/docs/00/07/15/33/PDF/RR-5050.pdf) (PDF), *Algorithmic number theory*, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, pp. 411–425, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.107.8612](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.8612), [doi](/source/Doi_(identifier)):[10.1007/978-3-540-24847-7_31](https://doi.org/10.1007%2F978-3-540-24847-7_31), [ISBN](/source/ISBN_(identifier)) [978-3-540-22156-2](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-22156-2), [MR](/source/MR_(identifier)) [2138011](https://mathscinet.ams.org/mathscinet-getitem?mr=2138011), [S2CID](/source/S2CID_(identifier)) [3119374](https://api.semanticscholar.org/CorpusID:3119374), INRIA Research Report RR-5050. 1. **[^](#cite_ref-weilert_14-0)** Weilert, André (July 2000). ["(1+i)-ary GCD Computation in Z\[i\] as an Analogue to the Binary GCD Algorithm"](https://doi.org/10.1006%2Fjsco.2000.0422). *Journal of Symbolic Computation*. **30** (5): 605–617. [doi](/source/Doi_(identifier)):[10.1006/jsco.2000.0422](https://doi.org/10.1006%2Fjsco.2000.0422). 1. **[^](#cite_ref-eisenstein_15-0)** Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (12–15 August 2003). *Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers*. 14th International Symposium on the Fundamentals of Computation Theory. [Malmö](/source/Malm%C3%B6), Sweden. pp. 109–117. [doi](/source/Doi_(identifier)):[10.1007/978-3-540-45077-1_11](https://doi.org/10.1007%2F978-3-540-45077-1_11). 1. **[^](#cite_ref-some-quadratic-rings_16-0)** Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (13–18 June 2004). *Binary GCD Like Algorithms for Some Complex Quadratic Rings*. Algorithmic Number Theory Symposium. [Burlington, VT](/source/Burlington%2C_VT), USA. pp. 57–71. [doi](/source/Doi_(identifier)):[10.1007/978-3-540-24847-7_4](https://doi.org/10.1007%2F978-3-540-24847-7_4). 1. **[^](#cite_ref-UFD-quadratic-rings_17-0)** Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (20–24 March 2006). *A New GCD Algorithm for Quadratic Number Rings with Unique Factorization*. 7th Latin American Symposium on Theoretical Informatics. Valdivia, Chile. pp. 30–42. [doi](/source/Doi_(identifier)):[10.1007/11682462_8](https://doi.org/10.1007%2F11682462_8). 1. **[^](#cite_ref-integer-rings_18-0)** Wikström, Douglas (11–15 July 2005). *On the l-Ary GCD-Algorithm in Rings of Integers*. Automata, Languages and Programming, 32nd International Colloquium. Lisbon, Portugal. pp. 1189–1201. [doi](/source/Doi_(identifier)):[10.1007/11523468_96](https://doi.org/10.1007%2F11523468_96). ## Further reading - [Knuth, Donald](/source/Donald_Knuth) (1998). "§4.5 Rational arithmetic". *Seminumerical Algorithms*. [The Art of Computer Programming](/source/The_Art_of_Computer_Programming). Vol. 2 (3rd ed.). Addison-Wesley. pp. 330–417. [ISBN](/source/ISBN_(identifier)) [978-0-201-89684-8](https://en.wikipedia.org/wiki/Special:BookSources/978-0-201-89684-8). Covers the extended binary GCD, and a probabilistic analysis of the algorithm. - [Cohen, Henri](/source/Henri_Cohen_(number_theorist)) (1993). "Chapter 1 : Fundamental Number-Theoretic Algorithms". [*A Course In Computational Algebraic Number Theory*](https://books.google.com/books?id=hXGr-9l1DXcC). [Graduate Texts in Mathematics](/source/Graduate_Texts_in_Mathematics). Vol. 138. [Springer-Verlag](/source/Springer-Verlag). pp. 12–24. [ISBN](/source/ISBN_(identifier)) [0-387-55640-0](https://en.wikipedia.org/wiki/Special:BookSources/0-387-55640-0). Covers a variety of topics, including the extended binary GCD algorithm which outputs [Bézout coefficients](/source/B%C3%A9zout_coefficients), efficient handling of multi-precision integers using a variant of [Lehmer's GCD algorithm](/source/Lehmer's_GCD_algorithm), and the relationship between GCD and [continued fraction expansions](/source/Simple_continued_fraction) of real numbers. - [Vallée, Brigitte](/source/Brigitte_Vall%C3%A9e) (September–October 1998). ["Dynamics of the Binary Euclidean Algorithm: Functional Analysis and Operators"](https://web.archive.org/web/20110513012901/http://users.info.unicaen.fr/~brigitte/Publications/bin-gcd.ps). *Algorithmica*. **22** (4): 660–685. [doi](/source/Doi_(identifier)):[10.1007/PL00009246](https://doi.org/10.1007%2FPL00009246). [S2CID](/source/S2CID_(identifier)) [27441335](https://api.semanticscholar.org/CorpusID:27441335). Archived from [the original](https://users.info.unicaen.fr/~brigitte/Publications/bin-gcd.ps) (PS) on 13 May 2011. An analysis of the algorithm in the average case, through the lens of [functional analysis](/source/Functional_analysis): the algorithms' main parameters are cast as a [dynamical system](/source/Dynamical_system), and their average value is related to the [invariant measure](/source/Invariant_measure) of the system's [transfer operator](/source/Transfer_operator). ## External links - [NIST Dictionary of Algorithms and Data Structures: binary GCD algorithm](https://xlinux.nist.gov/dads/HTML/binaryGCD.html) - [Cut-the-Knot: Binary Euclid's Algorithm](https://www.cut-the-knot.org/blue/binary.shtml) at [cut-the-knot](/source/Cut-the-knot) - [*Analysis of the Binary Euclidean Algorithm*](https://wwwmaths.anu.edu.au/~brent/pub/pub037.html) (1976), a paper by [Richard P. Brent](/source/Richard_Brent_(scientist)), including a variant using left shifts v t e Number-theoretic algorithms Primality tests AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin Prime-generating Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization Integer factorization Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's Multiplication Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's Euclidean division Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT Discrete logarithm Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve Greatest common divisor Binary Euclidean Extended Euclidean Lehmer's Modular square root Cipolla Pocklington's Tonelli–Shanks Berlekamp Other algorithms Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system Italics indicate that algorithm is for numbers of special forms --- Adapted from the Wikipedia article [Binary GCD algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Binary_GCD_algorithm?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.