1
$\begingroup$

I'm busy writing a polynomial long division class in Java, and I see that Wikipedia provides a great example for performing the long division by hand. However, when I compare it to the provided pseudo-code a few lines further on, something doesn't look quite right in the pseudo-code. The given pseudo-code is as follows:

1    function n / d: 2      require d ≠ 0 3      (q, r) ← (0, n)            # At each step n = d × q + r 4      while r ≠ 0 AND degree(r) ≥ degree(d): 5         t ← lead(r)/lead(d)     # Divide the leading terms 6         (q, r) ← (q + t, r - (t * d)) 7      return (q, r) 

On line 6, the assignment for r is such that (t * d) is subtracted the entire r instead of just subtracting from the appropriate terms of r.

Am I correct in saying that line 6 of the pseudo-code is incorrect, and if so, what would be the correct way of stating it?

Note: A quick way to verify what I'm talking about is to use the example provided on the Wikipedia page. The first run (and subsequent runs) of the while-loop will yield an incorrect value for r.

  • 0
    Thanks Bill, please add that as an answer so that I can accept it. I didn't realise that the manual algorithm works only with the relevant terms as a matter of convenience, not as a matter of necessity.2012-10-17

2 Answers 2

2

Here subtracting from $r$ is the same as subtracting from the "appropriate" highest terms of $r$, viz the leading $n+1$ terms, where $n$ is the degree of the divisor. The inductive step of the polynomial division algorithm simply scales/leftshifts the divisor so its leading term matches the leading term of the dividend, so that they will cancel upon subtraction, in order to reduce the degree of the (new) dividend $\rm\:r-t\,d.\:$ Thus we need only perform the subtraction on the terms that match-up with the leftshifted divisor. The manual algorithm optimizes this by only copying down these pertinent terms.

Note that the loop invariant is $\rm\: n\, =\, q\,d + r\, =\, (q+t)\,d - t\,d + r\,\:$

which, in terms of fractions is $\rm\displaystyle\ \frac{n}d\, =\, q + \frac{r}d\, =\, q+t + \frac{r-t\,d}d$

so the inductive step simply pulls out highest term $\rm\,t\,$ from the quotient, then recurses on the remaining "simpler" quotient (with lower degree dividend).

1

The pseudo code is correct. Note that according to the comment in line 3, you want to maintain the equality $n=dq+r$. We quickly check that $d\cdot(q+t)+(r-td) = dq+dt+r-td=dq+r=n$ as required. The choice of $t$ is just important to ensure that the "new $r$", i.e. $r-td$ has lower degree than the old $r$.