Editing Synthetic division (section)

=== Compact Expanded Synthetic Division ===

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:

:<math>\dfrac{a_7 x^7 + a_6 x^6 + a_5 x^5 + a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0}{b_4 x^4 - b_3 x^3 - b_2 x^2 - b_1 x - b_0}</math>

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:

:<math>\begin{array}{cc} \begin{array}{rrrr} \\ \\ \\ \\ b_3 & b_2 & b_1 & b_0 \\ \\ &&&&/b_4 \\ \end{array} \begin{array}{|rrrr|rrrr} & & & & q_0 b_3 & & & \\ & & & q_1 b_3 & q_1 b_2 & q_0 b_2 & & \\ & & q_2 b_3 & q_2 b_2 & q_2 b_1 & q_1 b_1 & q_0 b_1 & \\ & q_3 b_3 & q_3 b_2 & q_3 b_1 & q_3 b_0 & q_2 b_0 & q_1 b_0 & q_0 b_0 \\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & q_2' & q_1' & q_0' & r_3 & r_2 & r_1 & r_0 \\ q_3 & q_2 & q_1 & q_0 & & & & \\ \end{array} \end{array}</math>

The following describes how to perform the algorithm; this algorithm includes steps for dividing non-monic divisors:

{{ordered list
|1=
Write the coefficients of the dividend on a bar.

:<math>\begin{array}{cc} \begin{array}{|rrrrrrrr} \ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline \end{array} \end{array}</math>

|2=
Ignoring the first (leading) coefficient of the divisor, negate each coefficients and place them on the left-hand side of the bar.

:<math>\begin{array}{cc} \begin{array}{rrrr} b_3 & b_2 & b_1 & b_0 \\ \end{array} & \begin{array}{|rrrrrrrr}\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline \end{array} \end{array}</math>

|3=
From the number of coefficients placed on the left side of the bar, count the number of dividend coefficients above the bar, starting from the rightmost column. Then place a vertical bar to the left, and as well as the row below, of that column. This vertical bar marks the separation between the quotient and the remainder.

:<math>\begin{array}{cc} \begin{array}{rrrr} b_3 & b_2 & b_1 & b_0 \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline & & & & & & & \\ \end{array} \end{array}</math>

|4=
Drop the first coefficient of the dividend below the bar.

:<math>\begin{array}{cc} \begin{array}{rrrr} b_3 & b_2 & b_1 & b_0 \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & & & & & & & \\ \end{array} \end{array}</math>

|5=
{{unordered list
|Divide the previously dropped/summed number by the leading coefficient of the divisor and place it on the row below (this doesn't need to be done if the leading coefficient is 1).<br />

In this case <math>q_3 = \dfrac{a_7}{b_4}</math>, where the index <math>3 = 7 - 4</math> has been chosen by subtracting the index of the divisor from the dividend.<br />

|Multiply the previously dropped/summed number (or the divided dropped/summed number) to each negated divisor coefficients on the left (starting with the left most); skip if the dropped/summed number is zero. Place each product on top of the subsequent columns.

:<math>\begin{array}{cc} \begin{array}{rrrr} \\ b_3 & b_2 & b_1 & b_0 \\ \\ &&&&/b_4 \\ \end{array} \begin{array}{|rrrr|rrrr} & q_3 b_3 & q_3 b_2 & q_3 b_1 & q_3 b_0 & & & \\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & & & & & & & \\ q_3 & & & & & & & \\ \end{array} \end{array}</math>
}}

|6=
Perform a column-wise addition on the next column. In this case, <math>q_2' = q_3 b_3 + a_6</math>.

:<math>\begin{array}{cc} \begin{array}{rrrr} \\ b_3 & b_2 & b_1 & b_0 \\ \\ &&&&/b_4 \\ \end{array} \begin{array}{|rrrr|rrrr} & q_3 b_3 & q_3 b_2 & q_3 b_1 & q_3 b_0 & & & \\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & q_2' & & & & & & \\ q_3 & & & & & & & \\ \end{array} \end{array}</math>

|7=
Repeat the previous two steps. Stop when you performed the previous two steps on the number just before the vertical bar.

{{ordered list |list_style_type=lower-roman
|1=
Let <math>q_2 = \dfrac{q_2'}{b_4}</math>.

:<math>\begin{array}{cc} \begin{array}{rrrr} \\ \\ b_3 & b_2 & b_1 & b_0 \\ \\ &&&&/b_4 \\ \end{array} \begin{array}{|rrrr|rrrr} & & q_2 b_3 & q_2 b_2 & q_2 b_1 & & & \\ & q_3 b_3 & q_3 b_2 & q_3 b_1 & q_3 b_0 & q_2 b_0 & & \\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & q_2' & q_1' & & & & & \\ q_3 & q_2 & & & & & & \\ \end{array} \end{array}</math>

|2=
Let <math>q_1 = \dfrac{q_1'}{b_4}</math>.

:<math>\begin{array}{cc} \begin{array}{rrrr} \\ \\ \\ b_3 & b_2 & b_1 & b_0 \\ \\ &&&&/b_4 \\ \end{array} \begin{array}{|rrrr|rrrr} & & & q_1 b_3 & q_1 b_2 & & & \\ & & q_2 b_3 & q_2 b_2 & q_2 b_1 & q_1 b_1 & & \\ & q_3 b_3 & q_3 b_2 & q_3 b_1 & q_3 b_0 & q_2 b_0 & q_1 b_0 & \\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & q_2' & q_1' & q_0' & & & & \\ q_3 & q_2 & q_1 & & & & & \\ \end{array} \end{array}</math>

|3=
Let <math>q_0 = \dfrac{q_0'}{b_4}</math>.

:<math>\begin{array}{cc} \begin{array}{rrrr} \\ \\ \\ \\ b_3 & b_2 & b_1 & b_0 \\ \\ &&&&/b_4 \\ \end{array} \begin{array}{|rrrr|rrrr} & & & & q_0 b_3 & & & \\ & & & q_1 b_3 & q_1 b_2 & q_0 b_2 & & \\ & & q_2 b_3 & q_2 b_2 & q_2 b_1 & q_1 b_1 & q_0 b_1 & \\ & q_3 b_3 & q_3 b_2 & q_3 b_1 & q_3 b_0 & q_2 b_0 & q_1 b_0 & q_0 b_0 \\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & q_2' & q_1' & q_0' & r_3 & & & \\ q_3 & q_2 & q_1 & q_0 & & & & \\ \end{array} \end{array}</math>
}}

|8=
Perform the remaining column-wise additions on the subsequent columns (calculating the remainder).

:<math>\begin{array}{cc} \begin{array}{rrrr} \\ \\ \\ \\ b_3 & b_2 & b_1 & b_0 \\ \\ &&&&/b_4 \\ \end{array} \begin{array}{|rrrr|rrrr} & & & & q_0 b_3 & & & \\ & & & q_1 b_3 & q_1 b_2 & q_0 b_2 & & \\ & & q_2 b_3 & q_2 b_2 & q_2 b_1 & q_1 b_1 & q_0 b_1 & \\ & q_3 b_3 & q_3 b_2 & q_3 b_1 & q_3 b_0 & q_2 b_0 & q_1 b_0 & q_0 b_0 \\ a_7 & a_6 & a_5 & a_4 & a_3 & a_2 & a_1 & a_0 \\ \hline a_7 & q_2' & q_1' & q_0' & r_3 & r_2 & r_1 & r_0 \\ q_3 & q_2 & q_1 & q_0 & & & & \\ \end{array} \end{array}</math>

|9=
The bottommost results below the horizontal bar are coefficients of the polynomials (the quotient and the remainder), where the coefficients of the quotient are to the left of the vertical bar separation and the coefficients of the remainder are to the right. These coefficients are interpreted as having increasing degree from right to left, beginning with degree zero for both the quotient and the remainder.<br />

We interpret the results to get:

:<math>\dfrac{a_7 x^7 + a_6 x^6 + a_5 x^5 + a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0}{b_4 x^4 - b_3 x^3 - b_2 x^2 - b_1 x - b_0} = q_3 x^3 + q_2 x^2 + q_1 x + q_0 + \dfrac{r_3 x^3 + r_2 x^2 + r_1 x + r_0}{b_4 x^4 - b_3 x^3 - b_2 x^2 - b_1 x - b_0}</math>

}}