Help with understanding the polynomial long division algorithm I saw this algorithm at Wikipedia:  
function n / d:
  require d ≠ 0
  (q, r) ← (0, n)            # At each step n = d × q + r
  while r ≠ 0 AND degree(r) ≥ degree(d):
     t ← lead(r)/lead(d)     # Divide the leading terms
     (q, r) ← (q + t, r - (t * d))
  return (q, r)

I have two  questions:


*

*What is the meaning of # At each step n = d × q + r? n is the polynomial that I want to divide, right? So why each step? I'm doing it just once ((q, r) ← (0, n)).

*What is lead(r)/lead(d)?? I mean what is the function lead() means?


Thank you!
 A: It seems to be recursively dividing using itself (the lead(r)/lead(d) line). "lead(r)" presumably means the leading term in the polynomial, so $x^2$ in $x^2+x+1$.
A: I'll expand a bit on my comment: For the (1), it means it's a relation that is true after each loop (a loop invariant, if you prefer). Suzu Hirose already answered for the (2).
The "while" stuff is called a loop. Just before you enter the loop, you have $n=dq+r$ because $r=n$ and $q=0$.
So, when you begin a loop, suppose you have $n=dq+r$.
After one step (one loop), you have a new value for $q$ and $r$, let's call the new values $q'$ and $r'$, and the old one keep their names $q$ and $r$.
The loop states:
$$q'=q+t$$
$$r'=r-td$$
Hence,
$$dq'+r'=d(q+t)+(r-td)=dq+r+dt-td=dq+r=n$$
That is, the value of $dq+r$ is the same when you enter the loop, and when you leave the loop (with the new values of $q$ and $r$).
That's exactly the definition of a loop invariant.
The extra feature of this loop, is that you have remove the term of highest degree in $r$ (the leading term), because the leading term of $td$ is the same as the leading term of $r$, thus when you subtract, it gets removed.
Thus, the loop repeatedly removes leading terms of $r$, while always preserving the property that $n=dq+r$. You are done when you can't remove leading terms any longer, and this happend when the degree of $r$ is less than the degree of $d$ (because when computing $t$ you would get a negative power of the variable, which is not correct).
All in all, you are left with a quotient and a remainder that satisfy $n=dq+r$ and $deg(r)<deg(d)$, and you have the result of polynomial long division of $n$ by $d$. Hurray.

As a side note, the result of division is necessarily unique, because, given any other pair $q_1,r_1$ that would satisfy $n=dq_1+r_1$, you would have, by subtracting, $d(q-q_1)+(r-r_1)=0$, and $r-r1$ is a multiple of $d$. If $deg(r)<deg(d)$ and $q\neq q_1$, then you must have $deg(r_1)\geq deg(d)$, since you will introduce a leading term of degree $deg(q-q_1)+deg(d)\geq deg(d)$.
