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

結論

この記事では、ホーナーの法則の3つのC++実装（反復（後方ループと前方ループ）、再帰）を紹介しました。再帰アプローチはエレガントですが、オーバーヘッドの削減により、反復メソッドは特に大きな多項式の場合、一般的に優れたパフォーマンスを提供します。最適な選択は、アプリケーションの特定のニーズと好みに依存しますが、ホーナーの法則を理解することは、効率的な多項式評価の鍵となります。