Évaluation polynomiale efficace avec la méthode de Horner en C++

La méthode de Horner fournit un moyen efficace d’évaluer les polynômes, en minimisant le nombre de multiplications nécessaires. Cela améliore considérablement les performances par rapport à l’approche naïve, en particulier pour les polynômes de degré supérieur. Cet article explore différentes implémentations C++ de la règle de Horner pour évaluer un polynôme de la forme :

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

Table des matières

• Approche itérative (boucle descendante)
• Approche itérative (boucle ascendante)
• Approche récursive
• Conclusion

Approche itérative (boucle descendante)

Cette implémentation reflète directement la structure de multiplication imbriquée de la règle de Horner à l’aide d’une boucle itérative descendante.

#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 << "La valeur du polynôme en x = " << x << " est : " << result << std::endl;
  return 0;
}

Approche itérative (boucle ascendante)

Bien que l’itération descendante soit plus intuitive, une boucle ascendante est tout aussi efficace. Cette version itère à partir du terme constant, construisant le résultat incrémentalement.

#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 << "La valeur du polynôme en x = " << x << " est : " << result << std::endl;
  return 0;
}

Approche récursive

La règle de Horner peut être élégamment implémentée de manière récursive, reflétant directement la structure de multiplication imbriquée. Cependant, pour les polynômes de très haut degré, les frais généraux d’appel de fonction peuvent avoir un impact sur les performances.

#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 << "La valeur du polynôme en x = " << x << " est : " << result << std::endl;
  return 0;
}

Conclusion

Cet article a présenté trois implémentations C++ de la règle de Horner : itérative (boucle descendante et ascendante) et récursive. Bien que l’approche récursive offre de l’élégance, les méthodes itératives offrent généralement de meilleures performances, en particulier pour les polynômes plus grands, en raison d’une réduction des frais généraux. Le choix optimal dépend des besoins et des préférences spécifiques de votre application ; cependant, la compréhension de la règle de Horner est essentielle pour une évaluation efficace des polynômes.