算法实现/数学/多项式求值

霍纳法则允许高效地计算任何多项式 p(x₀) 的值，对于任何多项式 p(x) = a₀ + a₁x + ... + a_nxⁿ 和值 x₀.

算法

与分别计算每个项的朴素方法不同，在霍纳法则中，你将多项式改写为 p(x) = a₀ + a₁x + ... + a_nxⁿ = a₀ + x(a₁ + x(a₂ + ... x(a_n))...))，然后使用递归方法来计算它对于特定 x₀ 的值。结果是一个需要 n 次乘法的算法，而不是朴素方法最佳变体需要的 2n 次乘法（如果每个 xⁱ 是单独计算的，则需要更多乘法）。

在下面的伪代码和每个实现中，多项式 p(x) 都表示为一个包含其系数的数组。

伪代码

输入：(a₀, ..., a_n)
输入：x₀
输出：p(x₀)

accum := 0
for i = n, n-1, n-2, ..., 2, 1, 0
     accum := x0(accum + ai)
return accum

C

float horner(float a[], int deg, float x0) {
   float accum = 0.0;
   int i;
   for (i=deg; i>=0; i--) {
      // equivalently using a fused multiply-add:
      // accum = fmaf(x0, accum, a[i]); 
      accum = x0*accum + a[i];
   }
   return accum;
}

Fortran F77

      real function horner(p,deg,x0)
      real p(*), x0
      integer deg

      horner = 0.0
      do 10 i=deg,0,-1
          horner = x0*horner + p(i+1)
   10 continue
      return
      end

Python

from typing import List
def horner(a: List[float], x0: float) -> float:
    accum = 0.0
    for i in reversed(a):
        accum = x0 * accum + i
    return accum

变体

补偿霍纳方案是霍纳算法的一种变体，它补偿了浮点数的误差。它需要霍纳算法计算时间 1.5 倍，但精度是 2 倍。

循环展开可以与霍纳方案一起使用，以便一次评估多个乘法。这被称为 k 阶霍纳。

也存在非霍纳方案用于评估多项式：朴素方法、埃斯特林方法和因式分解。