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!

Github:

### References

#### Bibliography

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