ホーナーの方法

概要

多項式の解を求める際に、累乗と乗算をまとめて計算する方法。

サンプル

以下の関数がある。

f(x) = a*x*x*x + b*x*x + c*x + d

この関数の解を求めるには、単純には、以下の計算が必要となる。

• 乗算：6回
• 加算：3回

これをホーナーの方法では、以下のように式を変形する事で乗算の計算を減らす。

f(x) = ( (a*x + b) * x + c) * x + d

このサンプルの場合、以下の計算が必要となる。

• 乗算：3回
• 加算：3回

一般的には、n次の多項式における計算量は以下のようになる。