Effiziente Polynom-Auswertung mit dem Horner-Schema in C++

Das Horner-Schema bietet eine effiziente Methode zur Auswertung von Polynomen und minimiert die benötigten Multiplikationen. Dies verbessert die Performance im Vergleich zum naiven Ansatz erheblich, insbesondere bei Polynomen höheren Grades. Dieser Artikel untersucht verschiedene C++-Implementierungen der Horner-Regel zur Auswertung eines Polynoms der Form:

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

Inhaltsverzeichnis

• Iterativer Ansatz (rückwärts laufende Schleife)
• Iterativer Ansatz (vorwärts laufende Schleife)
• Rekursiver Ansatz
• Fazit

Iterativer Ansatz (rückwärts laufende Schleife)

Diese Implementierung spiegelt die geschachtelte Multiplikationsstruktur der Horner-Regel direkt mit einer rückwärts iterierenden Schleife wider.

#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 << "Der Wert des Polynoms an x = " << x << " ist: " << result << std::endl;
  return 0;
}

Iterativer Ansatz (vorwärts laufende Schleife)

Während die rückwärts gerichtete Iteration intuitiver ist, ist eine vorwärts gerichtete Schleife ebenso effizient. Diese Version iteriert vom konstanten Term aus und baut das Ergebnis inkrementell auf.

#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 << "Der Wert des Polynoms an x = " << x << " ist: " << result << std::endl;
  return 0;
}

Rekursiver Ansatz

Die Horner-Regel lässt sich elegant rekursiv implementieren, wobei die geschachtelte Multiplikationsstruktur direkt widergespiegelt wird. Bei Polynomen sehr hohen Grades kann der Funktionsaufruf-Overhead jedoch die Performance beeinträchtigen.

#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 << "Der Wert des Polynoms an x = " << x << " ist: " << result << std::endl;
  return 0;
}

Fazit

Dieser Artikel präsentierte drei C++-Implementierungen der Horner-Regel: iterativ (rückwärts und vorwärts laufende Schleifen) und rekursiv. Während der rekursive Ansatz Eleganz bietet, liefern die iterativen Methoden im Allgemeinen eine bessere Performance, insbesondere bei größeren Polynomen, aufgrund des reduzierten Overheads. Die optimale Wahl hängt von den spezifischen Anforderungen und Präferenzen Ihrer Anwendung ab; das Verständnis der Horner-Regel ist jedoch der Schlüssel zur effizienten Polynom-Auswertung.