# Horner's method A method for evaluation of polynomial $f(X)=a_0+a_1X+\cdots+a_nX^n$ at $x$: $f(x)=((\cdots((a_nx+a_{n-1})x+a_{n-2})x\cdots+a_0) $ This reduce the number of multiplications (counting both scalar and non-scalar) from $2n$ down to $n$. It achieves the optimal number of multiplications and additions. [[Paterson-Stockmeyer]] scheme minimizes the non-scalar multiplications of the evaluation down to $\sqrt{n}+\log(n)$ . Reference: - [Fast Matrix Multiplication](http://theoryofcomputing.org/articles/gs005/gs005.pdf) - [Horner's method Wikipedia](https://en.wikipedia.org/wiki/Horner%27s_method) ## Created 2023-12-06 10:36