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
.