Horner's Method of Synthetic Division
Polynomial division with remainder is a building block for many important algebraic algorithms. Horner's method of synthetic division
provides an efficient means of computing such quotients and remainders.
Given polynomials $f(x)$ and $g(x)$ in indeterminate $x$, we will compute polynomials
$q(x)$ (the quotient) and $r(x)$ (the remainder) such that $f(x)=g(x)q(x)+r(x)$ where either $r(x)=0$ or the degree of $r(x)$ is smaller than the degree of $g(x)$.
Specifically, the Horner's method table is created as follows:
- List the coefficients of $f(x)$ along the top row. These are listed from the leading coefficient down to the trailing coefficient.
- Place $g(x)$'s leading coefficient to the left of $f(x)$'s leading coefficient. [The first row is now completed.]
- Negate the remaining coefficients of $g(x)$ and list them (vertically) below $g(x)$'s leading coefficient. [The first column is now completed.]
- Draw a vertical line to the right of the $g(x)$'s data. Draw a horizontal line well below this data. [Note: It is possible to have more rows than the number of coefficients of $g(x)$. Also, it is possible to have less (non-empty) rows than than the number of $g(x)$'s coefficients.]
- In the next (uncompleted) column, sum up the entries in that column and divide by $g(x)$'s leading coefficient. Place this number below the horizontal line at the bottom of that column. [This column is now completed.]
- Take the number we just computed and multiply it by each of the negated coefficients of $g(x)$ (this is all of the coefficients of $g(x)$ except for the leading coefficient). Place these values in the next available (uncompleted) row. Starting in the next available uncompleted column. [Now this row is completed.]
- This process should continue until our multiples fill a row to its end.
- The remaining entries (below the horizontal line) at the bottom of uncompleted columns are computed by summing the entries in the column above. [This finishes the table.]
The bottom of the table just below the horizontal line is a list of coefficients of the quotient and remainder. The first $(\mathrm{deg}(f(x))-\mathrm{deg}(g(x))+1)$ numbers are the coefficients of the quotient $q(x)$ (listed from leading to trailing coefficient) and the remaining numbers are the coefficients of the remainder $r(x)$ (also listed from top to bottom).
Note: The polynomials can have coefficients in Sage's "symbolic ring" (i.e. SR). So coefficients such as "1+sqrt(2)" and "5+3*i" are allowed. The Sage code tries to clean up inputs (Ex: It changes (x-1)(x-2) to (x-1)*(x-2) and 3x to 3*x), but it cannot anticipate all syntax errors. As warning, check how your input was interpreted. It may also mis-correct certain inputs.
The computation above is powered by SageMath. The Sage code is embedded in this webpage's html file.
To view the code instruct your browser to show you this page's source.
For example, in Chrome, right-click and choose "View page source".
Wikipedia entry for Horner's method.