Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
But subtracting from $r$ is the same as subtracting from the appropriate terms of $r$. The manual algorithm works with only the pertinent terms simply as a matter of convenience. Note that the loop invariant is $\rm\: n = q\,d + r = (q+t)\,d - t\,d + r\ \ $ –  Bill Dubuque Oct 17 '12 at 17:04
    
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. –  Richard Keller Oct 17 '12 at 17:56

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.