Polynomial long division

I re-learned about long division with polynomials this week. It was kind of obvious that you can do this because if you can multiply polynomials it means that you can also divide them.

But the technique to actually doing it on the paper is interesting. It also adapts to the code, this code is taken from the wikipedia page "polynomial long division":

assert d != 0, "divide by zero"
q = 0
r = n # the whole polynomial is a remainder at first.
while r != 0 and degree(r) >= degree(d):
    t = lead(r) / lead(d) # dividing leading terms
    q = q + t
    r = r - t * d
return [q, r]

To get the degree(r) of a polynomial r, you have to pull the polynomial into its canonical form, and pick the degree of the largest term.

Monomials

The lead(r) returns a leading term of the polynomial, implying that there is an order between the terms. When you pick a term of a polynomial, the term is a monomial. Ordering between them is called 'monomial ordering'.

To get it into the right order here you have to order the terms by a degree, largest degree first. This way also calculating the degree of the polynomial is easy. It is always the leading term that has the highest degree.

Multivariate division

The above applies to polynomials with one variable, but division can be also defined on polynomials with multiple variables.

With multiple variables you have to consider division with multiple terms. The code would change to this:

assert d != 0, "divide by zero"
q = 0
r = n
while True:
    ld = lead(d)
    for m in r: # iterating through terms
        if is_divisible(m, ld):
            t = m / ld
            q = q + t
            r = r - t * d
            break
    else:
        return [q, r]

You divide until the remainder has no terms that can be divided by the leading term of the divider.

Theoretically you can even do such that you have multiple polynomials you use for division and you divide by them both simultaneously. Such as below:

assert d != 0, "divide by zero"
qs = [0] * len(D)
r = n
while True:
    for i, d in enumerate(D):
        ld = lead(d)
        for m in r:
            if is_divisible(m, ld):
                t = m / ld
                qs[i] = qs[i] + t
                r = r - t * d
                break
        else:
            continue
        break
    else:
        return [qs, r]

This has a problem that the remainder won't be unique in respect to the order of the division. Ordering the D in different ways may give you a different r.

If you read further about this subject, you eventually arrive to the concept of the gröbner basis. The idea there appears to be that if you:

Take the set of polynomials you have
Start producing so called s_polynomials from your set.
If the division of any s_polynomial(a,b) produces a nonzero remainder when divided(or reduced) by the set, add the remainder into the set.
Keep producing s_polynomials until you can no longer produce a s_polynomial from any pair in the set, that produces a nonzero remainder when divided by the set.

Then this new set produces the same results as the earlier set, except that it gives the same remainder irrespective of which order you take in dividing.

Here's the same in code:

while True:
    for i,j in pairs(G):
        r = reduce(s_polynomial(i,j), G).remainder
        if r != 0:
            break
    else:
        return G
    G.add(r)

I do not yet understand the applications of this all, but it seems to have been important for people who have written computer algebra systems.

Polynomial long division

Monomials

Multivariate division

Similar posts