Evaluación eficiente de polinomios con la regla de Horner en C++

El método de Horner proporciona una forma eficiente de evaluar polinomios, minimizando el número de multiplicaciones necesarias. Esto mejora significativamente el rendimiento en comparación con el enfoque ingenuo, especialmente para polinomios de grado superior. Este artículo explora varias implementaciones en C++ de la regla de Horner para evaluar un polinomio de la forma:

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

Tabla de contenido

• Enfoque iterativo (bucle hacia atrás)
• Enfoque iterativo (bucle hacia adelante)
• Enfoque recursivo
• Conclusión

Enfoque iterativo (bucle hacia atrás)

Esta implementación refleja directamente la estructura de multiplicación anidada de la regla de Horner utilizando un bucle de iteración hacia atrás.

#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 << "El valor del polinomio en x = " << x << " es: " << result << std::endl;
  return 0;
}

Enfoque iterativo (bucle hacia adelante)

Si bien la iteración hacia atrás es más intuitiva, un bucle hacia adelante es igualmente eficiente. Esta versión itera desde el término constante, construyendo el 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 << "El valor del polinomio en x = " << x << " es: " << result << std::endl;
  return 0;
}

Enfoque recursivo

La regla de Horner se puede implementar elegantemente de forma recursiva, reflejando directamente la estructura de multiplicación anidada. Sin embargo, para polinomios de grado muy alto, la sobrecarga de llamadas a funciones puede afectar el rendimiento.

#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 << "El valor del polinomio en x = " << x << " es: " << result << std::endl;
  return 0;
}

Conclusión

Este artículo presentó tres implementaciones en C++ de la regla de Horner: iterativa (bucles hacia atrás y hacia adelante) y recursiva. Si bien el enfoque recursivo ofrece elegancia, los métodos iterativos generalmente proporcionan un mejor rendimiento, especialmente para polinomios más grandes, debido a la reducción de la sobrecarga. La opción óptima depende de las necesidades y preferencias específicas de su aplicación; sin embargo, comprender la regla de Horner es clave para una evaluación eficiente de polinomios.