La función std::gcd en C++

1. Utilice la función std::gcd para calcular el máximo común divisor de dos enteros en C++
2. Utilice la función std::lcm para calcular el mínimo común múltiplo de dos enteros en C++
3. Utilice la función std::midpoint para calcular el punto medio de dos números en C++

Este artículo explicará cómo utilizar std::gcd y otras funciones matemáticas útiles de la biblioteca numérica STL en C++.

Utilice la función std::gcd para calcular el máximo común divisor de dos enteros en C++

STL proporciona múltiples algoritmos que utilizan el encabezado <algorithm>, pero también proporciona potentes funciones matemáticas, algunas de las cuales pueden considerarse algoritmos numéricos. Estas funciones se proporcionan mediante el encabezado - numeric.

Exploraremos la función std::gcd que calcula el máximo común divisor de dos enteros. Un máximo común divisor es el número entero positivo más grande que divide cada uno de los números enteros dados.

std::gcd toma dos valores enteros (m y n) y devuelve el máximo común divisor de |m| y |n|. Si tanto m como n tienen cero, la función también devuelve cero. El siguiente código de ejemplo demuestra el uso básico de std::gcd e imprime los resultados correspondientes en la consola.

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

Producción :

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

Utilice la función std::lcm para calcular el mínimo común múltiplo de dos enteros en C++

Otra función similar proporcionada en la biblioteca numérica es std::lcm, que calcula el mínimo común múltiplo de dos enteros. La función acepta dos enteros similares a std:gcd y devuelve el mínimo común múltiplo de |m| y |n| (que denota los argumentos).

Observe que ambas funciones tienen un especificador constexpr, lo que implica que es posible que se usen en expresiones constantes, y también la función obtiene una clasificación en línea.

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

Producción :

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

Utilice la función std::midpoint para calcular el punto medio de dos números en C++

std::midpoint es una función capaz de calcular la mitad de dos números dados sin que el usuario se preocupe por los desbordamientos. Es decir, si intentamos calcular la mitad de dos enteros grandes, cuya suma es mayor que el límite superior del entero de 64 bits, obtenemos el desbordamiento y el resultado será incorrecto.

Como ejemplo, el siguiente fragmento de código intenta encontrar el punto medio de dos enteros, donde uno es el mismo que el número máximo que se puede almacenar en uint64_t y el otro es menos en diez. Observe que el cálculo que utiliza los operadores aritméticos habituales produce un número incorrecto, mientras que std::midpoint devuelve el resultado correcto.

Sin embargo, tenga en cuenta que esta función ha sido parte del lenguaje desde el estándar C++ 20 y es posible que no esté disponible en versiones anteriores. std::midpoint también funciona con valores de puntero, pero los punteros dados deben ser elementos de la misma matriz. De lo contrario, el comportamiento no está definido.

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

Producción :

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