In this blog post, we explore polynomial division through a step-by-step example, explain why the method works, and implement the algorithm that performs polynomial division in Python.

Introduction

Polynomial division extends the idea of long division to polynomials. Just as we divide numbers to simplify expressions or solve equations, polynomial division helps break down complex polynomial expressions into more manageable parts. By dividing one polynomial by another, we can determine important information, such as roots, factors, and remainders.

Polynomial division plays a critical role in real-world applications. For instance, it’s a key element in error detection techniques like Cyclic Redundancy Check (CRC), which is used in networking and storage to detect errors in data transmission.

Long division of integers

Polynomial division is similar to the division of integers. For example, when dividing 10 (the dividend) by 3 (the divisor), the result is a quotient 3 with a remainder of 1. We can verify this by multiplying 3 by 3 and adding the remainder, giving us 10. Similarly, dividing 17 by 6 yields a quotient 2 and a remainder of 5, and multiplying 2 by 6, then adding 5, gives 17. In general, when dividing an integer \(a\) by an integer \(d\), we get a quotient \(q\) and remainder \(r\) such that:

Typically, we are interested in a quotient \(q\) such that \(r<d\).

Polynomial division

Polynomial division follows the same principles as integer division, but instead of numbers, we work with polynomials. Given a polynomial \(f(x)\) (the dividend) and another polynomial \(g(x)\) (the divisor), dividing \(f(x)\) by \(g(x)\) results in a quotient \(q(x)\) and a remainder \(r(x)\). This can be expressed as:

where the degree of the remainder \(r(x)\) is strictly less than the degree of the divisor \(g(x)\).

Example

Let’s walk through an example in which we divide the polynomial

by the polynomial

Step 1: Divide the Leading Terms

We begin by dividing the leading term of the dividend \(f(x)\) by the leading term of the divisor \(g(x)\):

This gives us the first term of our quotient \(q(x)=2x^4\).

Step 2: Multiply and Subtract (Determine the Remainder)

Next, we need to determine the remainder of the division. We know that

By rearranging the terms we get:

So we multiply the entire divisor \(g(x)\) by the term \(2x^4\) which we just found.

Then we subtract this product from the original dividend \(f(x)\). The difference of this operation is the remainder.

Step 3: Write Down the Result

A typical way to write down polynomial division on a paper is as follows:

We place the product of \(g(x)q(x)\) below \(f(x)\). We put a minus sign in front of the product to indicate that we are subtracting the polynomial on this line from the polynomial of the line above. We then subtract the terms of these polynomials and write the difference (the remainder) below a horizontal line.

Step 4: Repeat

If the degree of the remainder is greater or equal to the degree of the divisor \(g(x)\), we repeat the steps above by using the remainder we just found as the dividend for the next step and adding the quotient we get in the next step to the quotient of the previous step.

If the degree of the remainder is smaller than the degree of the divisor, we are done.

All steps performed

If we perform all steps for our example we finally get:

We can verify that the result is correct by adding the remainder to the product of the quotient and the divisor.

Why it Works

To understand the reason why we can divide polynomials iteratively by dividing the leading terms of the divisor and dividend, let’s do the polynomial division for the generic case. In the first iteration we divide the leading term of \(f(x)\) by the leading term of \(g(x)\) to get the quotient \(q_1(x)\) and the remainder \(r_1(x)\) such that

We compute \(f(x) - g(x)q_1(x)\) to get the remainder \(r_1(x)\).

If \(\deg(r_1(x)) \geq \deg(g(x))\) we repeat this. However, in the next iteration, we divide the leading term of the remainder \(r_1(x)\) we found in the current iteration by the leading term of \(g(x)\). We get a new quotient \(q_2(x)\) and remainder \(r_2(x)\), such that

If we substitude \(r_1\) in \(f(x)\) we get

We repeat these steps and after \(j\) steps we have

We stop after step \(j\) when \(\deg(r_j(x)) < \deg(g(x))\). We finally got

This shows us that we can perform a polynomial division iteratively by just dividing the leading terms of the divisor and dividend where the remainder of one iteration becomes the divisor for the next iteration.

The algorithm is guaranteed to stop as with each iteration the degree of the remainder decreases.

Implementation

Now, that we know how to divide polynomials on paper we can write a program that implements the steps.

First, we need to parse mathematical expressions. To keep the code simple we allow only simple terms like the terms which occur in the expression \(-2x^2-x+3x-5\). These terms can have a sign followed by an optional coefficient, followed by the optional variable x. With the character ‘^’ we can specify the exponent of x. If the exponent is not specified, 1 is assumed.

import re 

# Simple parser that parses polynomial expressions
# like '-2x^2 - x + 3x - 5' into a list of tuples.
# It's so simple that it doesn't handle errors.
def parse_expression(s):
    def split_expresssion(s):
        return re.findall(r'[+-]?[^+-]+', s.replace(' ', ''))

    def parse_exponent(s):
        m = re.match(r'^x\^(\d+)$', s)
        return m.group(1) if m else 1

    def parse_term(term):
        m = re.match(r'^([+-]?\d*)(x.*)?$', term)
        coeff = -1 if m.group(1) == '-' else 1 if m.group(1) == '' else m.group(1)
        exponent = parse_exponent(m.group(2)) if m.group(2) else 0
        return int(coeff), int(exponent)

    return [parse_term(t) for t in split_expresssion(s)]

The function parse_expression first splits the expression into terms and then parses each term individually. For each term we get a tuple that contains the coefficient and the exponent of its variable.

Next, it’s useful to have a representation of the parsed polynomial that is easy to process. We can use an array for that. In that array we store the coefficient of \(x^i\) at position i. For instance, for the term \(3x^5\) we store the coefficient 3 at position 5. If the expression contains the terms with the same exponent multiple times, we just store the result. For instance, if the expressions contains something like \(3x^5+7x^5\) we store the value 10 at position 5.

The following code takes a list of (coefficient, exponent) tuples returned by parse_expression and returns an array.

def into_array(expression_tuples):
    # Determine the required size for the array.
    max_exponent = max([e for _, e in expression_tuples])
    arr = [0] * (max_exponent + 1)
    for c, e in expression_tuples:
        arr[e] += c
    return arr

We also implement a function that turns an array back into an expression so that we directly see the result of our polynomial division.

def as_string(arr):
    s = ''
    for exponent in range(len(arr) - 1, -1, -1):
        sign = '+' if arr[exponent] >= 0 else ''
        variable = '' if exponent == 0 else 'x' if exponent == 1 else f'x^{exponent}'
        if arr[exponent] != 0:
            s += f'{sign}{arr[exponent]:g}{variable}'
    # Remove leading '+' if present.
    return re.sub(r'^\+', '', s) if s else '0'

Now, we can finally implement the function that divides a polynomial \(a\) by a polynomial \(p\) and returns the quotient and the remainder of the division. Both polynomials are provided in our array representation.

def divide_polynomials(a, p):
    # Determines the term with the highes exponent
    # that has a non-zero coefficient.
    def leading_term(p):
        for i in range(len(p) - 1, -1, -1):
            if p[i] != 0:
                return p[i], i
        return -1, -1

    quotient = [0] * len(a)
    # Our initial remainder is the provided polynomial ´a´.
    remainder = a.copy()
    while True:
        # Repeat dividing remainder by p as long as the remainder
        # has a higher exponent than the divisor.
        r_coeff, r_exp = leading_term(remainder)
        p_coeff, p_exp = leading_term(p)
        if r_exp < p_exp:
            break
        # Divide leading term of ´a´ by leading term of ´p´.
        # We get a coefficient and exponent of the quotient.
        q_coeff, q_exp = r_coeff / p_coeff, r_exp - p_exp
        # Store the coefficient.
        quotient[q_exp] += q_coeff
        # Subtract quotient * p from current remainder to
        # get the new remainder.
        for i in range(len(p)):
            remainder[i + q_exp] -= q_coeff * p[i]
        # The coefficient of the leading term of the
        # remainder should become zero. However, due to
        # limited floating point precision, we might
        # need to set it to zero explicitly.
        remainder[r_exp] = 0
    return quotient, remainder

Now, we can write a function that parses the expressions, brings it into the array representation, divides the polynomials and returns the quotient and remainder.

def divide(a, p):
    a = into_array(parse_expression(a))
    p = into_array(parse_expression(p))
    return [as_string(p) for p in divide_polynomials(a, p)]

Now we can call that function as shown in the following

divide('4x^7+8x^3+7x+5', '2x^3+4x')

which returns the list ['2x^4-4x^2+12', '-41x+5'] with the quotient and remainder.

Conclusion

Polynomial division is a powerful technique that extends the principles of long division to polynomials which is useful for simplifying complex expressions and uncovering important insights such as roots and remainders. This post guided through the polynomial division process, illustrated each step with a detailed example and showed how to implement the algorithm in Python.