La fonction std::gcd en C++

1. Utilisez la fonction std::gcd pour calculer le plus grand diviseur commun de deux entiers en C++
2. Utilisez la fonction std::lcm pour calculer le plus petit commun multiple de deux entiers en C++
3. Utilisez la fonction std::midpoint pour calculer le point médian de deux nombres en C++

Cet article expliquera comment utiliser std::gcd et d’autres fonctions mathématiques utiles de la bibliothèque numérique STL en C++.

Utilisez la fonction std::gcd pour calculer le plus grand diviseur commun de deux entiers en C++

STL fournit plusieurs algorithmes utilisant l’en-tête <algorithm>, mais il fournit également de puissantes fonctions mathématiques, dont certaines peuvent être considérées comme des algorithmes numériques. Ces fonctions sont fournies à l’aide de l’en-tête - numeric.

Nous allons explorer la fonction std::gcd qui calcule le plus grand commun diviseur de deux entiers. Un plus grand diviseur commun est le plus grand entier positif qui divise chacun des entiers donnés.

std::gcd prend deux valeurs entières (m et n) et renvoie le plus grand diviseur commun de |m| et |n|. Si m et n ont tous deux zéro, la fonction renvoie également zéro. L’exemple de code suivant illustre l’utilisation de base de std::gcd et imprime les résultats correspondants sur la 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;
}

Production:

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

Utilisez la fonction std::lcm pour calculer le plus petit commun multiple de deux entiers en C++

Une autre fonction similaire fournie dans la bibliothèque numérique est std::lcm, qui calcule le plus petit commun multiple de deux entiers. La fonction accepte deux entiers similaires au std:gcd et renvoie le plus petit commun multiple de |m| et |n| (indiquant les arguments).

Notez que ces deux fonctions ont un spécificateur constexpr, ce qui implique qu’il est possible qu’elles soient utilisées dans des expressions constantes, et que la fonction obtient également une classification en ligne.

#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;
}

Production:

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

Utilisez la fonction std::midpoint pour calculer le point médian de deux nombres en C++

std::midpoint est une fonction capable de calculer la moitié de deux nombres donnés sans que l’utilisateur se soucie des débordements. A savoir, si nous essayons de calculer la moitié de deux grands entiers, dont la somme est supérieure à la limite supérieure de l’entier 64 bits, alors nous obtenons le débordement et le résultat sera incorrect.

À titre d’exemple, l’extrait de code suivant essaie de trouver le milieu de deux entiers, où l’un est le même que le nombre maximum pouvant être stocké dans uint64_t, et l’autre est inférieur de dix. Notez que le calcul utilisant les opérateurs arithmétiques habituels donne le mauvais nombre tandis que std::midpoint renvoie le résultat correct.

Notez cependant que cette fonction fait partie du langage depuis la norme C++20 et peut ne pas être disponible sur les anciennes versions. std::midpoint fonctionne également sur les valeurs de pointeur, mais les pointeurs donnés doivent être des éléments du même tableau. Sinon, le comportement n’est pas défini.

#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;
}

Production:

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