Jump to content

Algorithm Implementation/Mathematics/Polynomial evaluation

From Wikibooks, open books for an open world

Horner's method allows the efficient computation of the value of p(x0) for any polynomial p(x) = a0 + a1x + ... + anxn and value x0.

Algorithm

[edit | edit source]

Rather than the naive method of computing each term individually, in Horner's method you rewrite the polynomial as p(x) = a0 + a1x + ... + anxn = a0 + x(a1 + x(a2 + ... x(an))...)), and then use a recursive method to compute its value for a specific x0. The result is an algorithm requiring n multiplies, rather than the 2n multiplies needed by the best variant of the naive approach (and much more if each xi is computed separately).

In both the pseudocode and each implementation below, the polynomial p(x) is represented as an array of it's coefficients.

Pseudocode

[edit | edit source]

input: (a0, ..., an)
input: x0
output: p(x0)

accum := 0
for i = n, n-1, n-2, ..., 2, 1, 0
     accum := x0(accum + ai)
return accum
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

[edit | edit source]
      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

[edit | edit source]
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

Variants

[edit | edit source]

The Compensated Horner Scheme is a variant of Horner's Algorithm that compensates for floating-point inaccuracies. It takes 1.5x the time of normal Horner to calculate for 2x the accuracy.[1]

Loop unrolling can be used with Horner's Scheme to evalulate multiple multiplications at once. This is called a kth-order Horner.[2]

There are also non-Horner schemes for evalulating polynomials: the naive method, the Estrin method, and factorization.[2]

References

[edit | edit source]
  1. S. Graillat and Nicolas Louvet (2005). Compensated Horner Scheme
  2. a b Timothée Ewart, Francesco Cremonesi, Felix Schürmann, and Fabien Delalondre. 2020. Polynomial Evaluation on Superscalar Architecture, Applied to the Elementary Function ex. ACM Trans. Math. Softw. 46, 3, Article 28 (September 2020), 22 pages. https://doi.org/10.1145/3408893