Finding the greatest common factor, GCF (sometimes referred to as the greatest common divisor or greatest common denominator) of two integers is a problem you may come across in embedded programming. Trying all combinations might work for small integers, but it will not be efficient if the integers are large. There is however a better way, first described by Euclid in his famous mathematical treatise “Elements” published around 300BC.
Let’s use the example of 527 and 221. These are both factors of 17 (17 × 31 = 527 and 17 × 13 = 221). If we are just given these two numbers and have to find the GCF we can use this method. Euclid’s algorithm is based on the idea that the common divisor does not change if the larger number is replaced by the difference between the larger and smaller numbers.
In our example we would replace 527 with 527 – 221 = 306. Now we have 306 and 221 which must have the same GCF as before. We continue to do this until the two numbers are equal, leaving us with the GCF as shown in Table 1. It takes 8 steps until the two numbers are equal and we arrive at the GCD of 17.
Here are the steps for Euclid’s algorithm to find the GCF of 527 and 221. At each step we replace the larger number with the difference between the larger and smaller numbers. We keep doing this until the two numbers are equal. What remains is the GCF.
Code Snippet 1 shows how this would be implemented in C. We replace the larger number with the smaller iteratively number until the numbers are equal. You can run this code on an on-line compiler to validate the results and play around with different inputs. For example, the GCF of 209,112,903 and 7,162,28 is 981.
/* Euclids Algorithm - Code Snippet 1 */
#include <stdio.h>
int euclid_1(int a, int b)
{
while (a != b)
{
if(a > b)
{
a = a - b;
}
else
{
b = b - a;
}
}
return a; /* could return b since they are equal */
}
int main()
{
int a = 527;
int b = 221;
printf("euclid_1(%d, %d) = %d", a, b, euclid_1(a, b));
return 0;
}This algorithm will be quite slow if one number is very large compared to the other, as many subtractions may be before the two approach each other. We could improve the efficiency of the algorithm if we replace the larger number with the remainder that’s left if we divide the two numbers. Let’s see how this works.
Using our simple example, 527 ÷ 221 = 2 with a remainder of 85. We replace the divisor 527 with the dividend 221 and the dividend with the remainder 85. Now our two numbers are 221 and 85. Repeating the process, 221 ÷ 85 = 2 remainder 51, so our two numbers become 81 & 55. We repeat the process until the two numbers are equal (or until b = 0) as shown in the upper part of Table 2. We can put this in code as shown in Code Snippet 2. Notice that we make use of the modulus operator % to calculate the remainder in a single operation.
— ADVERTISMENT—
—Advertise Here—
The steps for the improved algorithm are shown in the upper table. At each step we replace the larger number a with the smaller number, and the smaller number with the remainder of the division of a by b. We continue until a = b or b = 0 at which time a contains the GCF. The lower table shows if we start with a < b the since the algorithm effectively switches them in the first step, so we can continue as per the upper table.
/* Euclids Algorithm - Code Snippet 2 */
int euclid_1(int a, int b)
{
while (a != b)
{
if(a > b)
{
a = a - b;
}
else
{
b = b - a;
}
}
return a; /* could return b since they are equal */
}In the example above we assumed that the variable a held the larger of the two integers and b the smaller. A nice thing about this algorithm is that this does not have to be the case as illustrated in the lower part of Table 2. Here, we start with a = 221 and b = 527. 221 ÷ 527 = 0 remainder 221, so the dividend a becomes 527 and the divisor b becomes the remainder or 221. We now have a = 527 and b = 221 as for the previous example, and the process continues as before.
We could also implement this algorithm in a recursive manner as shown in. Code Snippet 3. The euclid_3 function is called at each iteration and the remainder calculation and variable shuffling is achieved by setting the function parameters appropriately. This is neat, and a great illustration of the power of recursive programs, but not particularly memory-efficient in this case if many iterations are required.
/* Euclids Algorithm - Code Snippet 3 */
#include <stdio.h>
int euclid_3(int a, int b)
{
int r;
if(b == 0){ return a; }
return euclid_3(b, a % b);
}
int main()
{
int a = 527;
int b = 221;
printf("euclid_3(%d, %d) = %d", a, b, euclid_3(a, b));
return 0;
}References
“Euclidean Algorithm.” In Wikipedia, April 12, 2022. https://en.wikipedia.org/w/index.php?title=Euclidean_algorithm&oldid=1082366720.
Khan Academy. “The Euclidean Algorithm (Article).” Accessed June 14, 2022. https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm.
“Online Compiler – C/C++, Java, Python… | Techie Delight.” Accessed June 14, 2022. https://techiedelight.com/compiler/.
— ADVERTISMENT—
—Advertise Here—
Andrew Levido (andrew.levido@gmail.com) earned a bachelor’s degree in Electrical Engineering in Sydney, Australia, in 1986. He worked for several years in R&D for power electronics and telecommunication companies before moving into management roles. Andrew has maintained a hands-on interest in electronics, particularly embedded systems, power electronics, and control theory in his free time. Over the years he has written a number of articles for various electronics publications and occasionally provides consulting services as time allows.
