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!