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).

Loading
Help | Powered by SageMath

Messages

Specifically, the Horner's method table is created as follows:

The bottom of the table just below the horizontal line is a list of coefficients of the quotient and remainder. The first   (deg(f(x))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.