Greatest Common Divisor and Least Common Multiplexer | Hello World
This is a very interesting problem, lets say we have m and n two (positive) integers, how to get the greatest Common Divisor and Least Common Multiplexer?
Lets start from Greatest Common Divisor(gcd) first. To find the gcd, we need to find all the prime factors for m and n, then multiply all the common part, then we get the gcd. Besides this elementary methods, we could use the Euclid algorithm
The Euclidean algorithm is a way to find the greatest common divisor of two positive integers, a and b. First let me show the computations for a=210 and b=45.
Divide 210 by 45, and get the result 4 with remainder 30, so 210=4·45+30.
Divide 45 by 30, and get the result 1 with remainder 15, so 45=1·30+15.
Divide 30 by 15, and get the result 2 with remainder 0, so 30=2·15+0.
The greatest common divisor of 210 and 45 is 15.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public class Test { public static int getGCD(int a, int b) { if (a == 0 || b == 0) return 0; if (a == b) return a; int l = Math.max(a, b); // a is the larger one int s = Math.min(a, b); // b is the smaller one if (l % s == 0) return s; return getGCD(l%s, s); } public static void main(String [] args) { int res = getGCD(42, 56); }} |
In plain English: the GCD of the two numbers large and small can be recursively calculated as large%small and the small. The base case ends when large%small == 0, in which case the small will be the GCD.
Formal description of the Euclidean algorithm
Input Two positive integers, a and b.
Output The greatest common divisor, g, of a and b.
Internal computation
If a<b, exchange a and b.
Divide a by b and get the remainder, r. If r=0, report b as the GCD of a and b.
Replace a by b and replace b by r. Return to the previous step.
Why does the algorithm stop?
At each step, the remainder, r, decreases by at least 1. Therefore r must eventually be 0. A formal proof would use mathematical induction
Read full article from Greatest Common Divisor and Least Common Multiplexer | Hello World
No comments:
Post a Comment