horner's method

Horner's method

Horner’s method is an efficient algorithm for evaluating polynomials. It rewrites a polynomial in a nested form to minimize the number of multiplications required.

$$f(x)=a_0+a_{1}x+a_2{x}^2+\dots +a_n{x}^n=(((a_{n}x+a_{n-1})x+a_{n-2})\cdots )x+a_0$$

This nested form allows the polynomial to be evaluated using only $n$ multiplications and $n$ additions, making it more efficient than the standard form, which requires $n(n+1)/2$ multiplications, or $2n-1$ with incremental powers.