Let \(F\) be the field. We consider a polynomial over the field. . \[p:=\cases{ F\to F\\ x\to p(x):=a_nx^n + \ldots + a_1x + a_0,\\ }\]

where \(a_0,a_1,\ldots,a_n\in F\) and assume that \(p\) is a polynomial of degree \(n\), i.e. \(a_n\neq 0\). Horner scheme is an algorithm for calculating the value \(p(x_0)\) at a specific value \(x\in F\). The algorithm \(\mathtt{horner}(n,x,a)\) requires \(\mathcal O(n)\) (worst case and average case) multiplication and addition operations.

Algorithm: Horner Scheme

def horner(n,a,x): h = a[n] for i in range(n-1, -1, -1): h = h*x + a[i]

  return h

Usage for x^3 + 2x^2 + 3x + 4, calculation of the polynom value for x=1:

a = [4, 3, 2, 1] n = len(a)-1 x = 1 print(horner(n,a,x))

  1. will output
  2. will output

Proofs: 1 2

Definitions: 1

Thank you to the contributors under CC BY-SA 4.0!




  1. Stummel, F; Hainer, K: "Praktische Mathematik", Teubner, 1982, 2nd Edition
  2. Hermann, D.: "Algorithmen Arbeitsbuch", Addison-Wesley Publishing Company, 1992