多項式の計算で乗算を増やさない方法 - 更新しない備忘録改二数値計算なんかをプログラムで書いてると、多項式の値を求めたいことがよくある。 たとえば次の多項式 これを計算するコードは、たとえば次のようになる。 // C/C++ f = x*x + 2*x + 3; もう少し一般的に、次の多項式 について、と係数の配列からを計算する関数を考える。 double poly1(double x, double a[], int n) { double f = 0.0; for (int i = 0; i <= n; i++) { double g = a[i]; for (int j = 0; j < i; j++) g *= x; f += g; } return f; } これでもいいのだが、次数の高い多項式を計算しようとすると、この関数の計算量は非常に大きくなる。 理由は簡単で、各を直接乗算で求めているからだ。 たとえばこの関数で100次の多項式を計
