|
The binary GCD algorithm is an algorithm 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. While the algorithm was first published in modern times by Josef Stein in 1961, it may have been known in first century China (Knuth, 1998). In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...
The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ...
In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...
1961 (MCMLXI) was a common year starting on Sunday (link will take you to calendar). ...
Concept
The algorithm reduces the problem of finding the GCD by repeatedly applying these identities: - If u = 0, then gcd(u,v) = v, since everything divides zero, and v is the largest number that divides v.
- 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.
- 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.
- If u is odd and v is even, then GCD(u,v) = GCD(u, v ÷ 2), similarly.
- 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 3 or 4 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.
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: The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ...
unsigned int gcd(unsigned int u, unsigned int v) { unsigned int k = 0; if (u == 0) return v; if (v == 0) return u; 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. Branch predication, not to be confused with branch prediction, is a strategy in computer architecture design for mitigating the costs usually associated with conditional branches, particularly branches to short sections of code. ...
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). The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
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 is its extended version (analogous to the extended Euclidean algorithm) as well-known or easily adaptable. An algorithm for the extended version is given on page 646 of (Knuth, 1998) along with pointers to other versions. The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ...
The extended Euclidean algorithm is an algorithm used to calculate the greatest common divisor (gcd, or also highest common factor, HCF) of two integers a and b, as well as integers x and y such that (This equation is known as Bezouts identity. ...
Implementations in other languages A simple functional version of the binary GCD algorithm, such as this version in ML, more directly reflects the original identities, but is inefficient unless modified to use tail recursion and the implementation transforms the multiplies, divides, and mod operations to bit operations: Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ...
ML is a general-purpose functional programming language developed by Robin Milner and others in the late 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM. Historically, ML stands for metalanguage as it was conceived to develop proof tactics in the LCF theorem prover (the language of...
In computer science, tail recursion is a special case of recursion that can be transformed into an iteration. ...
fun gcd(u,v) = if u = 0 then v (* Identity 5 *) else if u mod 2 = 0 andalso v mod 2 = 0 then 2*gcd(u div 2, v div 2) (* Identity 1 *) else if u mod 2 = 0 then gcd(u div 2, v) (* Identity 2 *) else if v mod 2 = 0 then gcd(u, v div 2) (* Identity 3 *) else if u >= v then gcd((u-v) div 2, v) (* Identity 4 *) else gcd(u, (v-u) div 2) (* Identity 4 *) This version of binary GCD in ARM assembly with GNU Assembler syntax highlights the benefit of branch predication: The ARM architecture (originally the Acorn RISC Machine) is a 32-bit RISC processor architecture that is widely used in a number of applications. ...
Gas (actually as, part of the Gnu Binutils package) is the default Gcc Back-end. ...
Branch predication, not to be confused with branch prediction, is a strategy in computer architecture design for mitigating the costs usually associated with conditional branches, particularly branches to short sections of code. ...
gcd: @ Arguments arrive in registers r0 and r1 mov r3, #0 @ Initialize r3, the power of 2 in the result orr r12, r0, r1 @ r12 = (r0 | r1) tst r12, #1 @ Test least significant bit of (r0 | r1) bne gcd_loop @ If nonzero, either r0 or r1 are odd, jump into middle of next loop remove_twos_loop: mov r0, r0, lsr #1 @ Shift r0 right, dividing it by 2 mov r1, r1, lsr #1 @ Shift r1 right, dividing it by 2 add r3, r3, #1 @ Increment r3 tst r0, #1 @ Check least significant bit of r0 bne gcd_loop @ If nonzero, r0 is odd, jump into middle of next loop tst r1, #1 @ Check least significant bit of r1 beq remove_twos_loop @ If zero, r0 and r1 still even, keep looping gcd_loop: @ Loop finding gcd of r0, r1 not both even tst r0, #1 @ Check least significant bit of r0 moveq r0, r0, lsr #1 @ If r0 is even, shift r0 right, dividing it by 2, and... beq gcd_loop_continue @ ... continue to next iteration of loop. tst r1, #1 @ Check least significant bit of r1 moveq r1, r1, lsr #1 @ If r1 is even, shift it right by 1 and... beq gcd_loop_continue @ ... continue to next iteration of loop. cmp r0, r1 @ Compare r0 to r1 subcs r2, r0, r1 @ If r0 >= r1, take r0 minus r1, and... movcs r0, r2, lsr #1 @ ... shift it right and put it in r0. subcc r2, r1, r0 @ If r0 < r1, take r1 minus r0, and... movcc r1, r2, lsr #1 @ ... shift it right and put it in r1. gcd_loop_continue: cmp r0, #0 @ Has r0 dropped to zero? bne gcd_loop @ If not, iterate mov r0, r1, asl r3 @ Put r1 << r3 in the result register bx lr @ Return to caller
See also In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...
In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ...
The Euclidean algorithm (also called Euclids algorithm) is an algorithm to determine the greatest common divisor (gcd) of two integers. ...
The extended Euclidean algorithm is an algorithm used to calculate the greatest common divisor (gcd, or also highest common factor, HCF) of two integers a and b, as well as integers x and y such that (This equation is known as Bezouts identity. ...
References Donald Knuth at a reception for the Open Content Alliance. ...
Cover of books The Art of Computer Programming is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ...
Charles Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ...
Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ...
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ...
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...
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
|
Feeds |
Contact