Fundamental Algorithms: Polynomial GCD

Another one in the series on fundamental algorithms; today: polynomial division. We assume, that polynomial is over some field, this is good thing, we have lots of nice properties in those; explicitly, if a and b are in the field and b is not zero, than there always exists an element of the field, c, such that a = bc.
So, division is easy, just "push it" over the field, like division in base, or multi precision division.
Algorithm, Knuth "The Art Computer Programming Vol 4" and the others:

# input: coefficients of polynomials as a lists u, v != 0
# in order u[0] = free coefficient of u(x), ....
# returns polynomials q, r such that u = vq + r(rest)
# length u >= length v >= 0
def poly_divide(u, v):
 m =   len(u) - 1
 n =   len(v) - 1
 q = [0] * (m - n + 1)
 lim = m - n
 for k in range(lim, -1, -1):
  q[k] = u[n + k] / v[n]
  for j in range(n + k - 1, k - 1, -1):
   u[j] = u[j] - q[k] * v[j - k]
 return q, u[:n]

Having division, we can compute the Great Common Divisor, showing, that Euclidean Domain is larger than expected:

def poly_gcd(u, v):
 if not any(v): return u
 else: return poly_gcd(v, poly_mod(u, v))

poly_mod  it's just a rest returned from division algorithm. I think it's beautiful, don't you?
The code, as usually on github , (division.py). Thank you, see you next time!