ホーナー法
係数 a n , a n − 1 , ⋯ , a 1 , a 0 {\displaystyle a_{n},a_{n-1},\cdots ,a_{1},a_{0}} からなる一変数 x の n 次多項式
p ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 {\displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}
の x = x 0 {\displaystyle x=x_{0}} における値 p ( x 0 ) {\displaystyle p(x_{0})} を求めることを考える。
直接的には、まず第一項 a n x n {\displaystyle a_{n}x^{n}} を計算し、次に第二項 a n − 1 x n − 1 {\displaystyle a_{n-1}x^{n-1}} を計算し、・・・と順番に計算して最後に足し合わせるという方法がある。ただし、この素朴な方法では、 n(n+1)/2 回の乗算が必要になってしまう。
一方で、上の多項式 p(x) は
p ( x ) = ( ⋯ ( a n x + a n − 1 ) x + ⋯ + a 1 ) x + a 0 {\displaystyle p(x)=(\cdots (a_{n}x+a_{n-1})x+\cdots +a_{1})x+a_{0}}
と変形することができる。この変形した状態で計算すると、乗算を n 回で済ませることができ、直接的な方法に比べて少ない演算の回数で多項式評価を行うことができる。この多項式評価の方法をホーナー法(Horner's rule)と言う。