Эффективная вычисление полиномов с помощью схемы Горнера на C++

Метод Горнера предоставляет эффективный способ вычисления полиномов, минимизируя необходимое количество умножений. Это значительно улучшает производительность по сравнению с наивным подходом, особенно для полиномов высокой степени. В этой статье рассматриваются различные реализации правила Горнера на C++ для вычисления полинома вида:

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

Содержание

• Итеративный подход (обратный цикл)
• Итеративный подход (прямой цикл)
• Рекурсивный подход
• Заключение

Итеративный подход (обратный цикл)

Эта реализация напрямую отражает вложенную структуру умножения правила Горнера с использованием цикла с обратной итерацией.

#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 << "Значение полинома при x = " << x << " равно: " << result << std::endl;
  return 0;
}

Итеративный подход (прямой цикл)

Хотя обратная итерация более интуитивна, прямой цикл столь же эффективен. Эта версия итерируется от константного члена, наращивая результат инкрементально.

#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 << "Значение полинома при x = " << x << " равно: " << result << std::endl;
  return 0;
}

Рекурсивный подход

Правило Горнера может быть элегантно реализовано рекурсивно, напрямую отражая вложенную структуру умножения. Однако для полиномов очень высокой степени накладные расходы на вызов функции могут повлиять на производительность.

#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 << "Значение полинома при x = " << x << " равно: " << result << std::endl;
  return 0;
}

Заключение

В этой статье представлены три реализации правила Горнера на C++: итеративные (с прямым и обратным циклами) и рекурсивная. Хотя рекурсивный подход предлагает элегантность, итеративные методы обычно обеспечивают лучшую производительность, особенно для больших полиномов, из-за уменьшенных накладных расходов. Оптимальный выбор зависит от конкретных потребностей и предпочтений вашего приложения; тем не менее, понимание правила Горнера является ключом к эффективному вычислению полиномов.