Avaliação Eficiente de Polinômios com a Regra de Horner em C++

O método de Horner fornece uma maneira eficiente de avaliar polinômios, minimizando o número de multiplicações necessárias. Isso melhora significativamente o desempenho em comparação com a abordagem ingênua, especialmente para polinômios de grau superior. Este artigo explora várias implementações em C++ da regra de Horner para avaliar um polinômio da forma:

P(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀

Sumário

• Abordagem Iterativa (Loop Inverso)
• Abordagem Iterativa (Loop Direto)
• Abordagem Recursiva
• Conclusão

Abordagem Iterativa (Loop Inverso)

Esta implementação reflete diretamente a estrutura de multiplicação aninhada da regra de Horner usando um loop de iteração inversa.

#include <iostream>
#include <vector>

double hornerBackward(const std::vector<double>& coefficients, double x) {
  double result = coefficients.back(); 
  for (int i = coefficients.size() - 2; i >= 0; --i) {
    result = result * x + coefficients[i];
  }
  return result;
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerBackward(coefficients, x);
  std::cout << "O valor do polinômio em x = " << x << " é: " << result << std::endl;
  return 0;
}

Abordagem Iterativa (Loop Direto)

Enquanto a iteração inversa é mais intuitiva, um loop direto é igualmente eficiente. Esta versão itera a partir do termo constante, construindo o resultado incrementalmente.

#include <iostream>
#include <vector>

double hornerForward(const std::vector<double>& coefficients, double x) {
  double result = coefficients[0];
  for (size_t i = 1; i < coefficients.size(); ++i) {
    result = result * x + coefficients[i];
  }
  return result;
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerForward(coefficients, x);
  std::cout << "O valor do polinômio em x = " << x << " é: " << result << std::endl;
  return 0;
}

Abordagem Recursiva

A regra de Horner pode ser elegantemente implementada recursivamente, refletindo diretamente a estrutura de multiplicação aninhada. No entanto, para polinômios de grau muito alto, a sobrecarga de chamadas de função pode afetar o desempenho.

#include <iostream>
#include <vector>

double hornerRecursive(const std::vector<double>& coefficients, double x, int n) {
  if (n == 0) {
    return coefficients[0];
  } else {
    return x * hornerRecursive(coefficients, x, n - 1) + coefficients[n];
  }
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerRecursive(coefficients, x, coefficients.size() - 1);
  std::cout << "O valor do polinômio em x = " << x << " é: " << result << std::endl;
  return 0;
}

Conclusão

Este artigo apresentou três implementações em C++ da regra de Horner: iterativa (loops inverso e direto) e recursiva. Embora a abordagem recursiva ofereça elegância, os métodos iterativos geralmente fornecem melhor desempenho, especialmente para polinômios maiores, devido à redução da sobrecarga. A escolha ideal depende das necessidades e preferências específicas do seu aplicativo; no entanto, a compreensão da regra de Horner é fundamental para a avaliação eficiente de polinômios.