Synthetic division
The advantages of synthetic division are that it allows one to calculate without writing variables, it uses few calculations, and it takes significantly less space on paper than long division.
The first example is synthetic division with only a monic linear denominator
The previous two steps are repeated, and the following is obtained: Here, the last term (-123) is the remainder while the rest correspond to the coefficients of the quotient.
Hence the quotient and remainder are: The above form of synthetic division is useful in the context of the polynomial remainder theorem for evaluating univariate polynomials.
The advantage of calculating the value this way is that it requires just over half as many multiplication steps as naive evaluation.
An alternative evaluation strategy is Horner's method.
This method generalizes to division by any monic polynomial with only a slight modification with changes in bold.
Note that while it may not be displayed in the following example, the divisor must also be written with verbose coefficients.
) Using the same steps as before, perform the following division: We concern ourselves only with the coefficients.
Write the coefficients of the polynomial to be divided at the top.
Write in every coefficient but the first one on the left in an upward right diagonal (see next diagram).
Repeat the previous two steps until you would go past the entries at the top with the next diagonal.
Since there are two, the remainder has degree one and this is the two right-most terms under the bar.
The result of our division is: With a little prodding, the expanded technique may be generalised even further to work for any polynomial, not just monics.
with its leading coefficient (call it a): then using synthetic division with
But this often produces unsightly fractions which get removed later and is thus more prone to error.
As can be observed by first performing long division with such a non-monic divisor, the coefficients of
Let's illustrate by performing the following division: A slightly modified table is used: Note the extra row at the bottom.
(in this case, indicated by the /3; note that, unlike the rest of the coefficients of
is dropped as usual: and then the dropped value is divided by 3 and placed in the row below: Next, the new (divided) value is used to fill the top rows with multiples of 2 and 1, as in the expanded technique: The 5 is dropped next, with the obligatory adding of the 4 below it, and the answer is divided again: Then the 3 is used to fill the top rows: At this point, if, after getting the third sum, we were to try and use it to fill the top rows, we would "fall off" the right side, thus the third sum is the first coefficient of the remainder, as in regular synthetic division.
As in expanded synthetic division, the last two values (2 is the degree of the divisor) are the coefficients of the remainder, and the remaining values are the coefficients of the quotient: and the result is However, the diagonal format above becomes less space-efficient when the degree of the divisor exceeds half of the degree of the dividend.
Consider the following division: It is easy to see that we have complete freedom to write each product in any row as long as it is in the correct column, so the algorithm can be compactified by a greedy strategy, as illustrated in the division below: The following describes how to perform the algorithm; this algorithm includes steps for dividing non-monic divisors: We interpret the results to get: The following snippet implements Expanded Synthetic Division in Python for arbitrary univariate polynomials:
