演算法實現/數學/多項式求值

霍納法則允許高效地計算任何多項式 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 階霍納。

也存在非霍納方案用於評估多項式：樸素方法、埃斯特林方法和因式分解。