# Horner scheme

A method for obtaining the incomplete fraction and the remainder in the division of a polynomial \begin{equation}\label{eq:1} f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \end{equation} by a binomial $x-a$, where all the coefficients $a,a_0,\ldots,a_n$ lie in a certain field, e.g. in the field of complex numbers. Any polynomial $f(x)$ can be uniquely represented in the form $$f(x) = g(x)(x-a) + r$$ where $g(x) = b_{n-1}x^{n-1} + b_{n-2}x^{n-2} + \cdots + b_0$ is the incomplete fraction, while $r$ is the remainder which, according to the Bezout theorem, equals $f(a)$. The coefficients of $g(x)$ and $r$ are calculated by the recurrence formulas \begin{equation}\label{eq:2} \left.{ \begin{array}{c} b_{n-1} = a_n,\ \ b_{n-2} = a_{n-1} + a b_{n-1},\ \ldots\,,\ b_0 = a_1 + a b_1 \ ; \\ r = a_0 + a b_0 \end{array} }\right\rbrace\ \ . \end{equation}
The following table $$\begin{array}{|c|c|c|c|c|c|} \hline \\ a_n & a_{n-1} & \ldots & a_1 & a_0 \\ \hline \\ a & b_{n-1} & b_{n-2} & \ldots & b_0 \\ \hline \end{array}$$ whose upper line is given, while the lower line is filled in accordance with the formulas \eqref{eq:2}), is used in the computations. In fact, this method is identical with the method of Ch'in Chiu-Shao employed in medieval China. At the beginning of the 19th century it was rediscovered, almost simultaneously, by W.G. Horner  and P. Ruffini .