• Science • People
Non User
 • Locations • Timeline
Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Home > Binary GCD algorithm

 
The binary GCD algorithm is an algorithm published by J. Stein in 1967 which computes the greatest common divisor of two positive integers. It gains a measure of efficiency over the ancient Euclidean algorithm by avoiding divisions and replacing them with bitwise operations that are cheaper when operating on the binary representation used by modern computers. This is particularly critical on embedded platforms that have no direct processor support for division.

1 Concept

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

  1. If u = 0, then gcd(u,v) = v, since everything divides zero, and v is the largest number that divides v.
  2. If u is even and v is even, then GCD(u,v) = 2·GCD(u ÷ 2, v ÷ 2), since we know 2 is a common divisor.
  3. If u is even and v is odd, then GCD(u,v) = GCD(u ÷ 2, v), since we know 2 is not a common divisor.
  4. If u is odd and v is even, then GCD(u,v) = GCD(u, v ÷ 2), similarly.
  5. If u is odd and v is odd, then GCD(u,v) = GCD(|u-v| ÷ 2, v) = GCD(u, |u-v| ÷ 2). This is a combination of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of identity 2 or 3 above. We know the division by 2 is possible because the difference of two odd numbers is even. We choose the version that makes the new operand smallest.

2 The Algorithm

Following is a straightforward implementation of the algorithm in the C programming language, taking two positive arguments u and v and using only bit operations and subtraction. It first removes all common factors of 2 using identity 1, computes the gcd of the remaining numbers using identities 2 through 5, then combines these to form the final answer:

unsigned int gcd(unsigned int u, unsigned int v) { unsigned int k = 0; while ((u & 1) == 0 && (v & 1) == 0) { /* while both u and v are even */ u >>= 1; /* shift u right, dividing it by 2 */ v >>= 1; /* shift v right, dividing it by 2 */ k++; /* add a power of 2 to the final result */ } /* At this point either u or v (or both) is odd */ do { if ((u & 1) == 0) /* if u is even */ u >>= 1; /* divide u by 2 */ else if ((v & 1) == 0) /* else if v is even */ v >>= 1; /* divide v by 2 */ else if (u >= v) /* u and v are both odd */ u = (u-v) >> 1; else /* u and v both odd, v > u */ v = (v-u) >> 1; } while (u > 0); return v << k; /* returns v * 2^k */ }

Efficiency can be enhanced on platforms with special instructions to find the least significant 1 bit in a word, allowing trailing zero bits to be removed in much larger groups. The latter while loop also benefits greatly from branch predication, which enables it to avoid many of the expensive branches caused by the many conditionals.

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 2 times, 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).

Although this algorithm can outperform the traditional Euclidean algorithm on many platforms, its asymptotic performance is the same, it is considerably more complex, and it does not generalize to negative integers or other fields such as polynomials where division with remainder is defined, nor does it have an extended version analogous to the extended Euclidean algorithm.



Read more »

Topics: Binary GCD Algorithm, Concept, The Algorithm, Implementations...

Binary-coded decimalBCD" redirects here. For "Buoyancy Control Device" see Buoyancy compensator. Binary-coded decimal BCD is a numeral system used in computing and in electronics systems. In BCD, numbers are represented as a sequence of decimal digits in which each digit isBinaryIn mathematics and computer science, the binary (base-two) numeral system is a representation for numbers that uses only zeroes and ones as digits. In popular computing, a binary computer file is one that is not human-readable, especially when referring tBinary relationIn mathematics, the concept of binary relation is exemplified by such ideas as "is greater than" and "is equal to" in arithmetic, or "is congruent to" in geometry, or "is an element of" or "is a subset of" in set theory. Definition Formally, a binary rela
Binary functionIn mathematics, a binary function or function of two variables is like a function, except that it has two inputs instead of one. To be specific, suppose X Y and Z are sets. Suppose that, given any elements x of X and y of Y f ''x ''y is a unique element oBinary operationIn mathematics, a binary operation or binary operator is a calculation involving two input quantities and one kind of a specific operation. It is sometimes called a dyadic operation as well. Examples include the familiar arithmetic operations of addition,Binary prefixIn computing, Binary prefixes are often used to quantify large numbers where powers of two are more useful than powers of ten. They are written and pronounced identically to the SI prefixes, but each successive prefix is multiplied by 1024 (210) rather th
Binary andBinary searchBinary search tree
Binary treeBinary Synchronous TransmissionBinary notation
Binary starBinary codingBinary heap
Non User