A função std::gcd em C++

1. Use a função std::gcd para calcular o máximo divisor comum de dois inteiros em C++
2. Use a função std::lcm para calcular o mínimo múltiplo comum de dois inteiros em C++
3. Use a função std::midpoint para calcular o ponto médio de dois números em C++

Este artigo irá explicar como utilizar std::gcd e outras funções matemáticas úteis da biblioteca numérica STL em C++.

Use a função std::gcd para calcular o máximo divisor comum de dois inteiros em C++

STL fornece vários algoritmos usando o cabeçalho <algorithm>, mas também fornece funções matemáticas poderosas, algumas das quais podem ser consideradas algoritmos numéricos. Essas funções são fornecidas usando o cabeçalho - numérico.

Exploraremos a função std::gcd que calcula o máximo divisor comum de dois inteiros. O maior divisor comum é o maior número inteiro positivo que divide cada um dos números inteiros fornecidos.

std::gcd recebe dois valores inteiros (m e n) e retorna o maior divisor comum de |m| e |n|. Se tanto m como n tiverem zero, a função também retornará zero. O código de exemplo a seguir demonstra o uso básico de std::gcd e imprime os resultados correspondentes no 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;
}

Produção:

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 a função std::lcm para calcular o mínimo múltiplo comum de dois inteiros em C++

Outra função semelhante fornecida na biblioteca numérica é std::lcm, que calcula o mínimo múltiplo comum de dois inteiros. A função aceita dois inteiros semelhantes a std:gcd e retorna o mínimo múltiplo comum de |m| e |n| (denotando os argumentos).

Observe que ambas as funções têm especificador constexpr, o que implica que é possível que sejam usadas em expressões constantes, e também a função obtém classificação inline.

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

Produção:

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 a função std::midpoint para calcular o ponto médio de dois números em C++

std::midpoint é uma função capaz de calcular a metade de dois números dados sem que o usuário se preocupe com os overflows. Ou seja, se tentarmos calcular a metade de dois inteiros grandes, a soma dos quais é maior do que o limite superior do inteiro de 64 bits, obteremos o estouro e o resultado ficará incorreto.

Como exemplo, o fragmento de código a seguir tenta encontrar o ponto médio de dois inteiros, onde um é igual ao número máximo que pode ser armazenado em uint64_t e o outro é menor em dez. Observe que o cálculo usando os operadores aritméticos usuais produz o número errado, enquanto std::ponto médio retorna o resultado correto.

Porém, lembre-se de que esta função faz parte da linguagem desde o padrão C++ 20 e pode não estar disponível em versões anteriores. std::midpoint funciona em valores de ponteiro também, mas os ponteiros fornecidos devem ser elementos do mesmo array. Caso contrário, o comportamento é indefinido.

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

Produção:

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