C++17 - find the greatest common divisor, gcd, of two or more integers
Posted on October 25, 2019 by Paul
In this article, I will show you how to find the gcd - greatest common divisor of two or more integers with C++, by using two implementations of the classical Euclid algorithm. As a side note, the C++ standard library has a std::gcd function that can calculate the gcd of two numbers and I will also show you how to use the STL version. Implementing an algorithm from scratch is the best way to understand it, even though in practice one should use as much as possible the solution already provided by the language standard library.
There is also a video version of this tutorial:
By definition, the gcd of two or more integers, that are not all zero, is the largest positive integer that divides all these numbers. For example:
gcd(9, 15) = 3
gcd(9, 15, 21) = 3
gcd(0, 10) = 10It is also useful to define:
gcd(0, 0) = 0.Here are couple of properties of the gcd function:
1 gcd(a, b) = gcd(b, a),
2 gcd(a, b) = gcd(-a, b),
3 gcd(a, b) = gcd(|a|, |b|),
4 gcd(a, 0) = |a|.The Euclid algorithm, or method, uses the fact that for two positive integers a and b:
if a > b then
gcd(a, b) = gcd(a - b, b)Here is a worked example of using Euclid’s method to calculate gcd(15, 9):
gcd(15, 9) = gcd(15 - 9, 9),
gcd(6, 9) = gcd(9, 6),
gcd(9, 6) = gcd(9 - 6, 6),
gcd(3, 6) = gcd(6, 3),
gcd(6 - 3, 3) = gcd(3, 3),
gcd(3 - 3, 3) = gcd(0, 3),
gcd(0, 3) = 3.finally, we can write:
gcd(15, 9) = 3Please note that, in the above calculations, we’ve used properties (1) and (4) of the gcd function.
At this point, we can write a C++ driver function that will ensure that we are doing the actual calculations only for positive integers:
1 // Calculate the gcd of two integers using an iterative implementation of Euclid's algorithm
2 constexpr int gcd_iterative(int a, int b) {
3 // Use the fact that gcd(a, b) = gcd(|a|, |b|)
4 // to cover both positive and negative integers
5 if(a < 0) a = -a;
6 if(b < 0) b = -b;
7 // Use the fact that gcd(a, b) = gcd(b, a) and gcd(a, 0) = gcd(0, a) = a.
8 // Obs. this covers the case gcd(0, 0) = 0 too
9 if(a == 0) return b;
10 if(b == 0) return a;
11
12 // Use the Euclid algorithm to calculate gcd
13 return euclid_gcd_iterative(a, b);
14 }Next, we’ll implement the iterative version of Euclid’s algorithm:
1 constexpr int euclid_gcd_iterative(int a, int b) {
2 while(a > 0) {
3 if(a < b) {
4 swap(a, b);
5 }
6 a = a - b;
7 }
8 return b;
9 }In the above function, we keep subtracting b from a and swapping a with b if a is less than b, until a becomes zero, at which point b contains the answer.
Line 4 in the above function calls a swap function. In principle we can use std::swap from the standard library, however I chose to implement my own version, since we are doing a from scratch version of gcd. Here is the implementation of my swap function:
1 constexpr void swap(int &a, int &b) {
2 int tmp = a;
3 a = b;
4 b = tmp;
5 }Let’s test the above functions:
1 constexpr int gcd_iterative(int a, int b);
2
3 constexpr int euclid_gcd_iterative(int a, int b);
4 constexpr void swap(int &a, int &b);
5
6 // Calculate the gcd of two integers using an iterative implementation of Euclid's algorithm
7 constexpr int gcd_iterative(int a, int b) {
8 // ...
9 }
10
11 constexpr int euclid_gcd_iterative(int a, int b) {
12 // ...
13 }
14
15 constexpr void swap(int &a, int &b) {
16 // ...
17 }
18
19 int main() {
20 static_assert(gcd_iterative(15, 9) == 3);
21 static_assert(gcd_iterative(24, -8) == 8);
22 static_assert(gcd_iterative(5, 0) == 5);
23 static_assert(gcd_iterative(0, 5) == 5);
24 static_assert(gcd_iterative(0, 0) == 0);
25 }If you build the above program with a standard C++17 compiler you should get no error and all five tests should pass at compile time.
If you want to trigger error messages at compile time, you can modify the main function from the above code, e.g.:
1 // ...
2
3 int main() {
4 static_assert(gcd_iterative(15, 9) == -1, "EXPECTED : gcd(15,9) = 3");
5 static_assert(gcd_iterative(24, -8) == -1, "EXPECTED : gcd(15,9) = 3");
6 static_assert(gcd_iterative(5, 0) == -1, "EXPECTED : gcd(15,9) = 3");
7 static_assert(gcd_iterative(0, 5) == -1, "EXPECTED : gcd(15,9) = 3");
8 static_assert(gcd_iterative(0, 0) == -1, "EXPECTED : gcd(15,9) = 3");
9 }This is what I see, if I build the above program with GCC 9.2 on a macOS machine:
Next, let’s implement a recursive version of the Euclid algorithm. The driver function is basically the same, except that it will call euclid_gcd_recursive on line 13:
1 // Calculate the gcd of two integers using a recursive implementation of Euclid's algorithm
2 constexpr int gcd_recursive(int a, int b) {
3 // Use the fact that gcd(a, b) = gcd(|a|, |b|)
4 // to cover both positive and negative integers
5 if(a < 0) a = -a;
6 if(b < 0) b = -b;
7 // Use the fact that gcd(a, b) = gcd(b, a) and gcd(a, 0) = gcd(0, a) = a.
8 // Obs. this covers the case gcd(0, 0) = 0 too
9 if(a == 0) return b;
10 if(b == 0) return a;
11
12 // Use the Euclid algorithm to calculate gcd
13 return euclid_gcd_recursive(a, b);
14 }Next, we’ll implement the recursive version of Euclid’s algorithm:
1 constexpr int euclid_gcd_recursive(int a, int b) {
2 if(a > 0) {
3 if(a < b) {
4 return gcd_euclid_recursive(b - a, a);
5 }
6 return euclid_gcd_recursive(a - b, b);
7 }
8 return b;
9 }Finally, let’s modify the main function by adding compile time tests for the recursive algorithm:
1 constexpr int gcd_iterative(int a, int b);
2 constexpr int gcd_recursive(int a, int b);
3
4 constexpr int euclid_gcd_iterative(int a, int b);
5 constexpr int euclid_gcd_recursive(int a, int b);
6 constexpr void swap(int &a, int &b);
7
8 // Calculate the gcd of two integers using an iterative implementation of Euclid's algorithm
9 constexpr int gcd_iterative(int a, int b) {
10 // ...
11 }
12
13 constexpr int euclid_gcd_iterative(int a, int b) {
14 // ...
15 }
16
17 // Calculate the gcd of two integers using a recursive implementation of Euclid's algorithm
18 constexpr int gcd_recursive(int a, int b) {
19 // ...
20 }
21
22 constexpr int euclid_gcd_recursive(int a, int b) {
23 // ...
24 }
25
26 constexpr void swap(int &a, int &b) {
27 // ...
28 }
29
30 int main() {
31 static_assert(gcd_iterative(15, 9) == 3);
32 static_assert(gcd_iterative(24, -8) == 8);
33 static_assert(gcd_iterative(5, 0) == 5);
34 static_assert(gcd_iterative(0, 5) == 5);
35 static_assert(gcd_iterative(0, 0) == 0);
36
37 static_assert(gcd_recursive(15, 9) == 3);
38 static_assert(gcd_recursive(24, -8) == 8);
39 static_assert(gcd_recursive(5, 0) == 5);
40 static_assert(gcd_recursive(0, 5) == 5);
41 static_assert(gcd_recursive(0, 0) == 0);
42 }An optimization of the Euclid algorithm for calculating gcd is to replace the repetitive subtraction of b from a with the modulo operator. For example, this is the recursive version of the algorithm with the above optimization:
1 constexpr int euclid_gcd_recursive(int a, int b) {
2 if(a > 0) {
3 if(a < b) {
4 return gcd_euclid_recursive(b % a, a);
5 }
6 return euclid_gcd_recursive(a % b, b);
7 }
8 return b;
9 }I’ve moved the optimized version of the above functions to file named gcd.h.
It is interesting to implement a gcd function that finds the greatest common divisor of a collection of integers, e.g.:
1 #include "gcd.h"
2
3 #include <iostream>
4 #include <vector>
5 #include <stdexcept>
6
7 int gcd(const std::vector<int> &V) {
8 if(V.size() < 2) {
9 throw std::runtime_error("Error! Input vector must have at least 2 elements");
10 }
11
12 int gcd_tmp{};
13 for(const auto &elem : V) {
14 gcd_tmp = gcd_iterative(gcd_tmp, elem);
15 }
16 return gcd_tmp;
17 }
18
19 int main() {
20 std::vector<int> V{15, 9, 21};
21 std::cout << "gcd(V) = " << gcd(V) << " Expected 3!\n";
22
23 V.emplace_back(-17);
24 std::cout << "gcd(V) = " << gcd(V) << " Expected 1!\n";
25 }As promised, here is an example of using the standard library gcd implementation:
1 #include <numeric>
2
3 int main() {
4 static_assert(std::gcd(15, 9) == 3);
5 static_assert(std::gcd(24, -8) == 8);
6 static_assert(std::gcd(5, 0) == 5);
7 static_assert(std::gcd(0, 5) == 5);
8 static_assert(std::gcd(0, 0) == 0);
9 }What about using std::gcd with a collection of integers? While you can use the above example with a loop over a vector, a simpler approach is to use std::reduce:
1 #include <numeric>
2 #include <array>
3 #include <iostream>
4
5 int main() {
6 std::array data{-13, 26, -39, 13};
7 std::cout << "gcd(data) = " << std::reduce(data.begin(), data.end(), 0, std::gcd<int,int>) << " Expected : 13\n";
8 }Please note that the above example will not compile with GCC 9! It works with VS 2019, Clang 9 and GCC 10.
You can find the complete source code on the GitHub repository for this article.
If you want to learn more about C++17 I would recommend reading C++17 in Detail by Bartlomiej Filipek:
or, C++17 - The Complete Guide by Nicolai M. Josuttis:
