binary GCD algorithm
   HOME

TheInfoList



OR:

The binary GCD algorithm, also known as Stein's algorithm or the binary Euclidean algorithm, is an algorithm that computes the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of two nonnegative integers. Stein's algorithm uses simpler arithmetic operations than the conventional
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
; it replaces division with
arithmetic shift In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift (though it is not restricted to signed operands). The two basic types are the arithmetic left shift and the arithmetic right shift. For binary ...
s, 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 Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer ''n'', the integer to be factored, can be divided by each number in turn ...
by 2 in favour of a single bitshift and the
count trailing zeros In computer software and hardware, find first set (ffs) or find first one is a bit operation that, given an unsigned machine word, designates the index or position of the least significant bit set to one in the word counting from the least signific ...
primitive; this is functionally equivalent to repeatedly applying identity 3, but much faster; * expressing the algorithm iteratively rather than
recursively Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
: 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 In computer science, predication is an architectural feature that provides an alternative to conditional transfer of control, as implemented by conditional branch machine instructions. Predication works by having conditional (''predicated'') no ...
; hard-to-predict branches can have a large, negative impact on performance. Following is an implementation of the algorithm in
Rust Rust is an iron oxide, a usually reddish-brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture. Rust consists of hydrous iron(III) oxides (Fe2O3·nH2O) and iron(III) oxide-hydroxide (FeO(OH ...
exemplifying those differences, adapted from ''uutils'': pub fn gcd(mut u: u64, mut v: u64) -> u64


Efficiency

The algorithm requires O(''n'') steps, where ''n'' is the number of bits in the larger of the two numbers, as every 2 steps reduce at least one of the operands by at least a factor of 2. Each step involves only a few arithmetic operations (O(1) with a small constant); when working with word-sized numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of log₂(max(''u'', ''v'')), i.e. ''n''. However, the
asymptotic complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of this algorithm is O(n2), as those arithmetic operations (subtract and shift) each take linear time for arbitrarily-sized numbers (one machine operation per word of the representation). 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.


Extensions

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 In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
, fits in the first kind of extension, as 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 The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971.A. Schönhage and V. Strassen,Schnelle Multiplikation großer Zahlen, ''C ...
for fast integer multiplication. The binary GCD algorithm has also been extended to domains other than natural numbers, such as
Gaussian integers In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf /ma ...
,
Eisenstein integers In mathematics, the Eisenstein integers (named after Gotthold Eisenstein), occasionally also known as Eulerian integers (after Leonhard Euler), are the complex numbers of the form :z = a + b\omega , where and are integers and :\omega = \fr ...
, quadratic rings, integer rings of
number fields In mathematics, an algebraic number field (or simply number field) is an extension field K of the field of rational numbers such that the field extension K / \mathbb has finite degree (and hence is an algebraic field extension). Thus K is a ...
, and arbitrary unique factorisation domains.


Historical description

An algorithm for computing the GCD of two numbers was known in ancient China, under the
Han dynasty The Han dynasty (, ; ) was an imperial dynasty of China (202 BC – 9 AD, 25–220 AD), established by Liu Bang (Emperor Gao) and ruled by the House of Liu. The dynasty was preceded by the short-lived Qin dynasty (221–207 BC) and a warr ...
, 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 In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
.


See also

*
Euclidean algorithm In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
*
Extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
*
Least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bot ...


References

, answer to exercise 39 of section 4.5.2 .


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 Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a fast greatest common divisor, GCD algorithm, an improvement on the simpler but slower Euclidean algorithm. It is mainly used for big integers that have a representation as a string of d ...
, and the relationship between GCD and
continued fraction In mathematics, a continued fraction is an expression (mathematics), expression obtained through an iterative process of representing a number as the sum of its integer part and the multiplicative inverse, reciprocal of another number, then writ ...
expansions of real numbers. * An analysis of the algorithm in the average case, through the lens of
functional analysis Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. Inner product space#Definition, inner product, Norm (mathematics)#Defini ...
: the algorithms' main parameters are cast as a
dynamical system In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space. Examples include the mathematical models that describe the swinging of a ...
, and their average value is related to the
invariant measure In mathematics, an invariant measure is a measure that is preserved by some function. The function may be a geometric transformation. For examples, circular angle is invariant under rotation, hyperbolic angle is invariant under squeeze mapping, an ...
of the system's
transfer operator Transfer may refer to: Arts and media * ''Transfer'' (2010 film), a German science-fiction movie directed by Damir Lukacevic and starring Zana Marjanović * ''Transfer'' (1966 film), a short film * ''Transfer'' (journal), in management studies ...
.


External links


NIST Dictionary of Algorithms and Data Structures: binary GCD algorithm

Cut-the-Knot: Binary Euclid's Algorithm
at
cut-the-knot Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Math ...

''Analysis of the Binary Euclidean Algorithm''
(1976), a paper by
Richard P. Brent Richard Peirce Brent is an Australian mathematician and computer scientist. He is an emeritus professor at the Australian National University. From March 2005 to March 2010 he was a Federation Fellow at the Australian National University. His ...
, including a variant using left shifts {{DEFAULTSORT:Binary Gcd Algorithm Number theoretic algorithms Articles with example C code