Recently I’ve started to implement (or reimplement) the most common algorithms a software developer should know . One of the nicest books I found on this topic is Algorithms in C (Robert Sedgewick) . Of course, there is this and this, but lately I am more interested on the “implementation” side of things than on maths and theory .
Euclid’s Algorithm is an efficient method for calculating the greatest common divisor of two numbers (aka GCD) . The GCD of two numbers is considered the largest number that divides both of them (without leaving a reminder) .
Euclid’s algorithm is based on the principle that given two numbers a and b, if a is greater than b than the greatest common divisor of a and b is the same with the common divisor of b and (b – a) . If we transform the above property into “code” (actually pseudo-code) the algorithm looks like this:
|
1 2 3 4 5 6 |
FUNCTION GCD(num1, num2) WHILE num1 > 0 IF num1 < num2 SWAP (num1, num2) num1 := num1 - num2 RETURN num2 |
The above pseudo-code is called the subtraction-variant . We can of course replace the repetitive subtractions with one division . The division-based version looks like this (in pseudo-code):
|
1 2 3 4 5 6 |
FUNCTION GCD(num1, num2) WHILE num1 > 0 tmp := num1 num1 := num2 MOD num1 num2 := tmp RETURN num2 |
There is also a recursive version of the algorithm:
|
1 2 3 4 |
FUNCTION GCD(num1, num2) IF num1 <> 0 THEN RETURN GCD(num2 MOD num1, num1) RETURN num2 |
For this implementation I’ve written 4 functions that do the same thing (calculate the greatest common divisor) but in a slightly different manner:
| int gcd1(int num1, int num2); | The most naive implementation, using repeated subtractions . |
| int gcd2(int num1, int num2); | A more performance-wise implementation, that instead of using repeated subtractions is using divisions . |
| int gcd3(int num1, int num2); | Using a FOR loop instead of the classical WHILE loop . |
| int gcd4(int num1, int num2); | The recursive version of the algorithm . |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include <stdio.h> #include <stdlib.h> /** * @author Andrei Ciobanu * @date DEC 11, 2010 */ int gcd1(int num1, int num2); int gcd2(int num1, int num2); int gcd3(int num1, int num2); int gcd4(int num1, int num2); /** * Calculates the greatest common divisor . * @param num1 * @param num2 * @return The greatest common divisor of num1 and num2 */ int gcd1(int num1,int num2) { int tmp; while(num1 > 0) { if (num1 < num2) { /* Swap */ tmp = num1; num1 = num2; num2 = tmp; } num1 -= num2; } return num2; } /** * Calculates the greatest common divisor . (Instead of using multiple * substractions we use division) * @param num1 * @param num2 * @return The greatest common divisor of num1 and num2 */ int gcd2(int num1, int num2) { int tmp; while (num1 > 0) { tmp = num1; num1 = num2 % num1; num2 = tmp; } return num2; } /** * Calculates the greatest common divisor . (The same as gcd2 but instead * using a FOR loop) * @param num1 * @param num2 * @return The greatest common divisor of num1 and num2 */ int gcd3(int num1, int num2) { int tmp; for(num1 = abs(num1), num2 = abs(num2); num1 > 0; tmp = num1, num1 = num2 % num1, num2 = tmp); return num2; } /** * Calculates the greatest common divisor . (Recursive way) * @param num1 * @param num2 * @return The greatest common divisor of num1 and num2 */ int gcd4(int num1, int num2) { if (num1) { return gcd4(num2 % num1, num1); } return num2; } int main(int argc, char *argv[]) { printf("gcd1(%u, %u) = %un", 10, 25, gcd1(10, 25)); printf("gcd1(%u, %u) = %un", 100, 24, gcd1(100, 24)); printf("gcd2(%u, %u) = %un", 10, 25, gcd2(10, 25)); printf("gcd2(%u, %u) = %un", 100, 24, gcd2(100, 24)); printf("gcd3(%u, %u) = %un", 10, 25, gcd3(10, 25)); printf("gcd3(%u, %u) = %un", 100, 24, gcd3(100, 24)); printf("gcd4(%u, %u) = %un", 10, 25, gcd4(10, 25)); printf("gcd4(%u, %u) = %un", 100, 24, gcd4(100, 24)); return (0); } |
And the output when running the whole program is:
|
1 2 3 4 5 6 7 8 |
gcd(10, 25) = 5 gcd(100, 24) = 4 gcd2(10, 25) = 5 gcd2(100, 24) = 4 gcd3(10, 25) = 5 gcd3(100, 24) = 4 gcd4(10, 25) = 5 gcd4(100, 24) = 4 |
Note:
If you are interested to read about a more performance-wise way to find the greatest common divisor of two numbers you can read this article on Stein’s Algorithm .
Pingback: Euclid’s Algorithm: Reducing fraction to lowest terms « andreINC.net
Pingback: Binary GCD (Stein’s Algorithm) in C « andreINC.net
Pingback: Fraction reduction in Scala « andreINC.net