The std::gcd Function in C++

1. Use the std::gcd Function to Calculate Greatest Common Divisor of Two Integers in C++
2. Use the std::lcm Function to Calculate Least Common Multiple of Two Integers in C++
3. Use the std::midpoint Function to Calculate Middle Point of Two Numbers in C++

This article will explain how to utilize std::gcd and other useful mathematical functions from STL numerics library in C++.

Use the std::gcd Function to Calculate Greatest Common Divisor of Two Integers in C++

STL provides multiple algorithms using <algorithm> header, but it also provides powerful mathematical functions, some of which can be considered numeric algorithms. These functions are provided using the header - numeric.

We will explore the std::gcd function that computes the greatest common divisor of two integers. A greatest common divisor is the largest positive integer that divides each of the given integers.

std::gcd takes two integer values (m and n) and returns the greatest common divisor of |m| and |n|. If both m and n happen to have zero, the function also returns zero. The following example code demonstrates the basic usage of std::gcd and prints the corresponding results to the console.

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  std::vector<std::pair<int, int>> vec = {
      {12125, 1235}, {124, 1122}, {-1235, 321}, {12, 144}};

  for (const auto &item : vec) {
    cout << "Greatest common divisor of " << setw(5) << item.first << " and "
         << setw(5) << item.second << " is "
         << std::gcd(item.first, item.second) << endl;
  }

  return EXIT_SUCCESS;
}

Output:

Greatest common divisor of 12125 and  1235 is 5
Greatest common divisor of   124 and  1122 is 2
Greatest common divisor of -1235 and   321 is 1
Greatest common divisor of    12 and   144 is 1

Use the std::lcm Function to Calculate Least Common Multiple of Two Integers in C++

Another similar function provided in the numerics library is std::lcm, which calculates the least common multiple of two integers. The function accepts two integers similar to the std:gcd and returns the least common multiple of |m| and |n| (denoting the arguments).

Notice that both of these functions have constexpr specifier, which implies it is possible that they are used in constant expressions, and also the function gets inline classification.

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  std::vector<std::pair<int, int>> vec = {
      {12125, 1235}, {124, 1122}, {-1235, 321}, {12, 144}};

  for (const auto &item : vec) {
    cout << "Least common multiple of " << setw(5) << item.first << " and "
         << setw(5) << item.second << " is "
         << std::lcm(item.first, item.second) << endl;
  }

  return EXIT_SUCCESS;
}

Output:

Least common multiple of 12125 and  1235 is 2994875
Least common multiple of   124 and  1122 is 69564
Least common multiple of -1235 and   321 is 396435
Least common multiple of    12 and   144 is 144

Use the std::midpoint Function to Calculate Middle Point of Two Numbers in C++

std::midpoint is a capable function for calculating the half of two given numbers without the user worrying about the overflows. Namely, if we try to calculate the half of two large integers, the sum of which is bigger than the upper bound of the 64-bit integer, then we get the overflow, and the result will be incorrect.

As an example, the following code snippet tries to find the midpoint of two integers, where one is the same as the maximum number that can be stored in uint64_t, and the other one is less by ten. Notice that the calculation using the usual arithmetic operators yields the wrong number while std::midpoint returns the correct result.

Mind though that this function has been part of the language since the C++20 standard and may not be available on older versions. std::midpoint works on pointer values as well, but the given pointers should be elements of the same array. Otherwise, the behavior is undefined.

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

using std::cout;
using std::endl;
using std::setw;
using std::vector;

int main() {
  uint64_t a = std::numeric_limits<uint64_t>::max();
  uint64_t b = std::numeric_limits<uint64_t>::max() - 10;

  cout << "a: " << a << '\n'
       << "b: " << b << '\n'
       << "Incorrect: " << setw(20) << (a + b) / 2 << '\n'
       << "Correct  : " << setw(20) << std::midpoint(a, b) << endl;

  return EXIT_SUCCESS;
}

Output:

a: 18446744073709551615
b: 18446744073709551605
Incorrect:  9223372036854775802
Correct  : 18446744073709551610