ホーナー法

     f(x) = a0xn + a1xn-1 + a2xn-2 + ... + an-1x + an
          = ((...(( a0x + a1 )x + a2)x + ...)x + an-1)x + an

	式	回数（乗算）
[1]	y←a0xn ... y←y+a1xn-1 y←y+an-2x2 y←y+a2xn-2 y←y+an-1x y←y+a3xn-3 y←y+an	n+...+2+1+0 =n(n+1)/2
[2]	t←x, y←an+an-1*t ... t←t*x, y←y+an-2*t t←t*x, y←y+a2*t t←t*x, y←y+an-3*t t←t*x, y←y+a1*t t←t*x, y←y+an-4*t t←t*x, y←y+a0*t	1+2+2+...+2 = 1+2(n-1) = 2n-1
[3]	y←a0 ... y←y*x+a1 y←y*x+an-2 y←y*x+a2 y←y*x+an-1 y←y*x+a3 y←y*x+an	1+1+...+1 = n

1. アルゴリズム1
   • a_kx^n-kに必要な掛け算の回数: k

     式	掛け算の回数
     an	0
     an-1x	1
     an-2x2=an-2x× x	2
     an-3x3=an-3x× x× x	3
     ...	...
     akxn-k=ak× x × ... × x	k

   • y=a₀xⁿ+a₁x^n-1 +a₂x^n-2+... +a_n-1x +a_n の計算 アルゴリズム:

     y←a0xn	y=a0xn
     y←y+a1xn-1	y=a0xn+a1xn-1
     y←y+a2xn-2	y=a0xn+a1xn-1 +a2xn-2
     ...	...
     y←y+an-1x	y=a0xn+a1xn-1 +a2xn-2+... +an-1x
     y←y+an	y=a0xn+a1xn-1 +a2xn-2+... +an-1x +an

     y=0

     k=0

     while(k<=n) y=y+ak*xn-k k=k+1

   ---

2. アルゴリズム2

   t←x, y←an+an-1*t	t=x, y=an+an-1x
   t←t*x, y←y+an-2*t	t=x2, y=an+an-1x+an-2x2
   t←t*x, y←y+an-3*t	t=x3, y=an+an-1x+an-2x2 +an-3x3
   ...	...
   t←t*x, y←y+a0*t	t=xn, y=an+an-1x +an-2x2 +an-3x3 +... +a0xn

   t=x

   y=an+an-1*t

   k=n-1

   while(k>=0) t=t*x y=y+ak*t k=k-1

   ---

3. アルゴリズム3 (ホーナー法)

   y←a0	y=a0
   y←y*x+a1	y=(a0)*y+a1 =a0y+a1
   y←y*x+a2	y=(a0x+a1)y+a2 =a0x2+a1x+a2
   ...	...
   y←y*x+an-1	y=(a0xn-2+a1xn-3 +...+an-2)*x+an-1 =a0xn-1 +a1xn-2 +a2xn-3 +... +an-2x+an-1
   y←y*x+an	y=(a0xn-1+a1xn-2 +...+an-1)*x+an =a0xn +a1xn-1 +a2xn-2 +... +an-2x2 +an-1x+an

   y=a0 k=1 while(k<= n) y=y*x+ak k=k+1	y=a[0]; k=1; while(k<=n) { y=y*x+a[k]; k=k+1; }
   y=a0 for k=1〜n y=y*x+ak	y=a[0]; for(k=1; k<=n; k++) y=y*x+a[k];

プログラム例

n次多項式(n<32) y=a₀xⁿ+a₁x^n-1 +a₂x^n-2 +a₃x^n-3 +... +a_n-2x² +a_n-1x +a_n の計算

ただし、次数n、係数a_k, (k=0,1,2,...,n) および x の 値はキーボード（標準入力装置）より読み込む。

---

準備 main() { 変数の宣言 次数nの値を読み込む 係数a0, a1, ..., an の値を読み込む xの値を読み込む ホーナー法により、yの値を求める yの値を書き出す }

#include < stdio.h> #define NMAX 32 main() { int n, k; double x, y, a[NMAX]; printf("次数 n: "); scanf("%d", &n); for(k=0; k<=n; k++) { printf("a[k]: "); scanf("&lf", &a[k]); } printf("x: "); scanf("&lf",x); y=a[0]; for(k=1; k<=n; k++) y=y*x+a[k]; printf("&lf\n", y); }