以下是一个典型的多项式运算
int y = 4*x*x*x*x +9*x*x*x +2*x*x +7*x +1;
这个表达式能不能性能优化？
细数一下这个表达式用了4+3+2+1=10次乘法，同时用到了4次加法。
可以优化为
int y = (((4*x+9)*x+2)*x+7)*x+1;
优化后，只有4次乘法和4次加法。直接减少了6次乘法运算。
这就是霍纳法则，也叫秦九韶算法，最早由中国人发明，用于减少多项式的计算次数。
霍纳法则原理很简单，缓存重复运算的结果，但是不是动态规划思想，因为不包含递归。
y
=
a
x
4
+
b
x
3
+
c
x
2
+
d
x
+
e
y=ax^4+bx^3+cx^2+dx+e
y=ax4+bx3+cx2+dx+e
合并
a
x
4
+
b
x
3
ax^4+bx^3
ax4+bx3包含的乘以
x
3
x^3
x3重复运算：
(
a
x
+
b
)
x
3
+
c
x
2
+
d
x
+
e
(ax+b)x^3 +cx^2+dx+e
(ax+b)x3+cx2+dx+e
进一步合并乘以
x
2
x^2
x2重复运算：
(
(
a
x
+
b
)
x
+
c
)
x
2
+
d
x
+
e
((ax+b)x+c)x^2+dx+e
((ax+b)x+c)x2+dx+e
进一步合并乘以x重复运算，得到结果，本质是空间换时间：
(
(
(
a
x
+
b
)
x
+
c
)
x
+
d
)
x
+
e
(((ax+b)x+c)x+d)x+e
(((ax+b)x+c)x+d)x+e
代码实现就非常简单了
public static int horner(int[] args, int x) {
int r = args[0];
for (int i = 1; i < args.length; i++) {
r = r * x + args[i];
}
return r;
}
python代码如下：
# _*_ coding:utf-8 _*_
class HornerPolynomial:
def __init__(self, items: list):
self.__polynomial = items
@property
def polynomial(self):
return self.__polynomial
# 本身是个函数
def __call__(self, *args, **kwargs):
result = 0
for coefficient in self.polynomial:
result = result * args[0] + coefficient
return result
那霍纳法则实用在哪里？
1 java String类的hashcode使用霍纳法则计算
2 用切比雪夫近似值计算sin(x) cos(x)时也用到了霍纳法则
3 开发工具生成得hashcode代码用到了霍纳法则。
尤其是切比雪夫近似值的优化，霍纳法则的使用可以说支撑了整个游戏世界。因为3D游戏中的投影计算中，大量使用了正弦余弦。但是计算机的正弦余弦都是用多项式近似值去计算的。只要用到多项式，必用霍纳法则。
对于计算机来说，乘法的开销远远大于加法，所以减少乘法次数非常重要，常见的减少乘法次数的算法还有矩阵strassen算法，二进制快速幂，Karatsuba算法等。
