计算机科学中，有一些关于多项式求值的问题。对于多项式求值问题，我们最容易想到的算法是求出每一项的值然后把所求的值累加起来，这种算法的时间和空间效率都不高，对于数据规模不大的题目来说由于其直观、简单很容易被大家采纳，可一旦数据规模过大时，这种算法就显得无能为力了，下面介绍一种解决这类求值问题的高效算法――霍纳法则。在中国，霍纳法则也被称为秦九韶算法。

假设有n＋2个实数$a_0$，$a_1$，…，$a_n$,和x的序列，要对多项式$P_n(x)= a_nx_n ＋a_{n－１}x_{n－１}＋…＋a_１x＋a_０$求值，直接方法是对每一项分别求值，并把每一项求的值累加起来，这种方法十分低效，它需要进行$n＋(n－1)＋…＋1＝n(n＋１)/2$次乘法运算和n次加法运算。有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法，即

$$P_n(x)= a_nx_n ＋a_{n－１}x_{n－１}＋…＋a_１x＋a_０\＝((…(((a_nx＋a_{n－１})x＋a_{n－２})x+ a_{n－3})…)x＋a_1)x＋a_０$$

这种求值的安排我们称为霍纳法则。

例如，当x=3时，计算$p(x)=2x^4－x^3＋3x^2＋x－5$的值。对于多项式$p(x)=2x^4－x^3＋3x^2＋x－5$，我们按霍纳法则进行变换，有：

$$p(x)=2x^4－x^3＋3x^2＋x－5 \=x(2x^3－x^2＋3x＋1)－5 \ =x(x(2x^2－x＋3)＋1)－5 \ =x(x(x(2x－1)＋3)＋1)－5$$

在实际的操作过程中，为了得到上式，我们没有必要经过上述的特定变换，我们只需要一个该多项式系数的原始列表。我们可以方便地用一个二维表格来帮助我们笔算求出这个多项式的值。该表第一行包含了该多项式的系数（如果存在等于0的系数，也都包含进来），从最高的$a_n$到最低的$a_0$。第二行中除了第一个和第二个单元格用来存储x和$a_n$外，其它单元格都用来存储中间结果。在作了这样的初始化后，在计算第二行的某一个单元格的值时，用该单元格的前一个单元格乘以x的值再加上该单元格的第一行的系数即可。用这种方式算出的最后一个单元格的值，就是该多项式的值。

系数 $a_4$ $a_3$ $a_2$ $a_1$ $a_0$
2 －1 3 1 －5
x=3 2 3*2－1=5 3*5+3=18 3*18+1=55 3*55－5=160

所以，P(3)=160。我们拿表格中的单元格和多项式$x(x(x(2x－1)＋3)＋1)－5$做比较，我们会发现$32-1=5$是$2x－1$在x=3时的值，$35+3=18$是$x(2x-1)+3$在x=3时的值，$318+1=55$是$x(x(2x-1)＋3)＋1$在x=3时的值，最后$355－5=160$是$x(x(x(2x－1)＋3)＋1)－5$在x=3时的值。

该算法在计算p(x)在某些点$x_0​$上的值时所产生的中间数字，恰好可以作为p(x)除以$x-x_0​$的商的系数，而算法的最后结果，除了等于$p(x_0)​$外，还等于这个除法的余数。因此，对于我们的例子来说，$p(x)=2x^4－x^3＋3x^2＋x－5​$除以$x-3​$的商和余数分别为$2x^3＋5x^2＋18x+55​$和160.这种除法算法被称为“综合除法”，要比所谓的“长除法”更方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
% a quick demo of Horner's method and its effects 
clear all 
close all 

% first a comparison of ways to compute 
x = 0.988:.0001:1.012; 
y1 = x.^7-7*x.^6+21*x.^5-35*x.^4+35*x.^3-21*x.^2+7*x-1; 
plot(x,y1,'r--') 
pause 

% because this polynomial can be nicely factored ... 
y2 = (x-1).^7; 
plot(x,y2) 
pause 

% now let's see Horner's method 
y3=-1+x.*(7+x.*(-21+x.*(35+x.*(-35+x.*(21+x.*(-7+x)))))); 
plot(x,y3) 
pause 

% now for the head-to-head comparison 
plot(x,y1,'r--',x,y3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//源程序
#include <iostream>
 
using namespace std;

//实现代码
int horner(int *a, int n,int x) //霍纳规则
{
    int ax = a[n] * x + a[n - 1];   //求出在内层括号内的值
    for(int i = n - 2; i >= 0; i--) //循环求出多项式在x处的值
    {
        ax = ax * x + a[i];
    }
    return ax;
}
 
int main()
{
    //测试
    int a[] = {3,0,2,0,3,5}; //数组a存储的是系数，该方程式=5x^5+3x^4+2x^2+3
    cout << horner(a,5,2) << endl;  //当x=2时 A(x)=219
    return 0;
}

参考资源