多項式の計算アルゴリズム

数学的なプログラムを作っていると、多項式の計算が必要なことがありますよね？

どうやって実装しますか？

あ、ちなみにこれ割と有名なやつなんで、アルゴリズムが好きな人なら大抵知ってるネタです。

インターフェース

まず関数のインターフェースを決めましょう。
変数をx、係数をa_i、次数をnとして
poly(x, a, n) = a₀x⁰ + a₁x¹ + a₂x² + ... + a_nxⁿ
を計算する関数のプロトタイプをC言語で作ってみましょう。

double poly(double x, double *a, int n);

普通の実装

まず素直に実装してみます。ループごとにxⁱを計算して、a_i + xⁱを足し合わせます。

double poly(double x, double *a, int n)
{
  double v = 0;
  for(int i = 0; i <= n; i++) {
    // x^i
    double xi = 1;
    for(int j = 0; j < i; j++) {
      xi *= x;
    }

    // a[i] * x^i
    v += a[i] * xi;
  }
  return v;
}

この方法だと計算量はO(n²)です。

速い実装

例えばa₀x⁰ + a₁x¹ + a₂x² を a₀ + x(a₁ + x(a₂)) のように計算すれば、計算量はO(n)で済みます。

double poly_horner(double x, double *a, int n)
{
  double v = a[n--];
  while(n >= 0) {
    v = v * x + a[n--];
  }
  return v;
}

速いうえにコード量もかなり減りましたね。これはHorner法と呼ばれています。