Polynomial long division & GCD

This is my go at Exercise 2.11 in A Programmer’s Introduction to Mathematics. The task was to write an implementation of the extended Euclidean algorithm to find the greatest common divisor of two polynomials.

This took me way longer than it maybe should have. Implementing polynomial long division with reference to the “long division” notation was not very straightforward, and required constant checking of the intermediate output, especially because I wanted to use while loops instead of keeping track of the iterations.

I hope this is somewhere in the ballpark of an elegant solution 😅

Polynomial long division

import typing

def poly_longdiv(dividend: Polynomial, divisor: Polynomial) -> Polynomial:
    '''This function assumes the arguments are the author's implementation of
    Polynomials in `Programmer's Intro to Mathematics`, which orders the terms
    ascending by degree.
    '''
    dividend = list(reversed(dividend.coefficients))
    divisor = list(reversed(divisor.coefficients))
    remainder = dividend
    quotient = []
    while True:
        quo = remainder[0] / divisor[0]
        quotient.append(quo)
        bottom = [quo * term for term in divisor]
        remainder = [top - bot for top, bot in zip(remainder, bottom)][1:]
        try:
            remainder.append(dividend[len(quotient) + len(divisor) - 1])
        except(IndexError):
            return {"quotient": Polynomial(list(reversed(quotient))),
                    "remainder": Polynomial(list(reversed(remainder)))}

See here for the author’s implementation of the Polynomial class.

Polynomial greatest common divisor

Meanwhile, this was pretty straightforward once I found this super-concise explanation. The Wikipedia article was incomprehensible.

def poly_gcd(a: Polynomial, b: Polynomial) -> Polynomial:
    '''Find the GCD of two polynomials using the Extended Euclidean algorithm.
    '''
    [small, big] = sorted([a, b], key=lambda x: len(x))
    division = big / small
    q, r = division["quotient"], division["remainder"]
    while r:
        big, small = small, r
        division = big / small
        q, r = division["quotient"], division["remainder"]
    return small

Update: And just for completeness, regular GCD with integers (copied from Geeks for Geeks):

def gcd(a: int, b: int) -> int:
    '''Find the GCD of two integers using the Extended Euclidean algorithm.
    '''
    [small, big] = sorted([a, b])
    while small:
        big, small = small, big % small
    return big

Rewriting my answer:

def poly_gcd(a: Polynomial, b: Polynomial) -> Polynomial:
    '''Find the GCD of two polynomials using the Extended Euclidean algorithm.
    '''
    [small, big] = sorted([a, b], key=lambda x: len(x))
    while small:
        big, small = small, (big / small)["remainder"]
    return big

Go Top