Efficient Polynomial Evaluation with Horner’s Rule in C++

Horner’s method provides an efficient way to evaluate polynomials, minimizing the number of multiplications needed. This significantly improves performance compared to the naive approach, especially for higher-degree polynomials. This article explores various C++ implementations of Horner’s rule for evaluating a polynomial of the form:

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

Table of Contents

• Iterative Approach (Backward Loop)
• Iterative Approach (Forward Loop)
• Recursive Approach
• Conclusion

Iterative Approach (Backward Loop)

This implementation directly reflects Horner’s rule’s nested multiplication structure using a backward-iterating loop.

#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 << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

Iterative Approach (Forward Loop)

While the backward iteration is more intuitive, a forward loop is equally efficient. This version iterates from the constant term, building the result incrementally.

#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 << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

Recursive Approach

Horner’s rule can be elegantly implemented recursively, directly mirroring the nested multiplication structure. However, for very high-degree polynomials, the function call overhead can impact performance.

#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 << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

Conclusion

This article presented three C++ implementations of Horner’s rule: iterative (backward and forward loops) and recursive. While the recursive approach offers elegance, the iterative methods generally provide better performance, especially for larger polynomials, due to reduced overhead. The optimal choice depends on your application’s specific needs and preferences; however, understanding Horner’s rule is key to efficient polynomial evaluation.