Binary GCD Algorithm - Algorithm


The algorithm reduces the problem of finding the GCD by repeatedly applying these identities:

  1. gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.
  2. If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
  3. If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
  4. If u and v are both odd, and uv, then gcd(u, v) = gcd((uv)/2, v). If both are odd and u < v, then gcd(u, v) = gcd((vu)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.
  5. Repeat steps 2–4 until u = v, or (one more step) until u = 0. In either case, the GCD is 2kv, where k is the number of common factors of 2 found in step 2.

The algorithm requires O((log2 uv)2) worst-case time, or in other words time proportional to the square of the number of bits in u and v together. Although each step reduces at least one of the operands by at least a factor of 2, the subtract and shift operations do not take constant time for very large integers (although they're still quite fast in practice, requiring about one operation per word of the representation).

An extended version of binary GCD, analogous to the extended Euclidean algorithm, is given in The Art of Computer Programming, along with pointers to other versions.

Read more about this topic:  Binary GCD Algorithm

Other articles related to "algorithm":

Markov Chain Monte Carlo - Random Walk Algorithms
... are some random walk MCMC methods Metropolis–Hastings algorithm Generates a random walk using a proposal density and a method for rejecting proposed moves ... Multiple-try Metropolis A variation of the Metropolis–Hastings algorithm that allows multiple trials at each point ... This allows the algorithm to generally take larger steps at each iteration, which helps combat problems intrinsic to large dimensional problems ...
Algorithm - History: Development of The Notion of "algorithm" - History After 1950
... toward further refinement of the definition of "algorithm", and activity is on-going because of issues surrounding, in particular, foundations of mathematics ... For more, see Algorithm characterizations ...
Barcode Reader - New Algorithms For Barcode Decoding - Symbology Decoding Algorithm
... The Symbology Decoding Algorithm for barcode scanners is the first symbology-based algorithm for decoding ... information from the entire image to detect transitions in the signal, whereas the traditional algorithm relies on the maxima and minima ... The Symbology Decoding Algorithm for Bar Code Scanners exhibited high resilience to blur and noise when tested on 1D Universal Product Codes ...
Timeline Of Algorithms - 1960s
... Hoare 1962 - Ford–Fulkerson algorithm developed by L ... Fulkerson 1962 - Bresenham's line algorithm developed by Jack E ... Fedorenko 1965 - Cooley–Tukey algorithm rediscovered by James Cooley and John Tukey 1965 - Levenshtein distance developed by Vladimir Levenshtein 1965 - Cocke–Younger–Kasami ...
Tomasulo Algorithm
... The Tomasulo algorithm is a hardware algorithm developed in 1967 by Robert Tomasulo from IBM ... This algorithm differs from scoreboarding in that it utilizes register renaming ... The Tomasulo algorithm also uses a common data bus (CDB) on which computed values are broadcast to all the reservation stations that may need it ...