Synthetic division calculator

Question

I've written a python program do perform synthetic division on a polynomial. There are a few constraints (listed in the module docstring of the program) on the polynomial, mainly because I haven't had the time to work out all the edge cases. I would like feedback on everything possible, as I plan to use this to solve other polynomials. All feedback is welcome, appreciated, and considered!

Constraints

1. Coefficients must only be one digit, if present

2. Constant must be one digit, and must be present (even 0)

3. Constant must be positive

synthetic_division.py

"""

SYNTHETIC DIVISION CALCULATOR

This program accepts a polynomial and returns all the
x intercepts.

Program has some constraints:
    - Coefficients must only be one digit, if present
    - Constant must be one digit, and must be present (even 0)
    - Constant must be positive

EX:
    Input: x^3 -4x^2 +x +6
    Output: X = [3, -1, 2]

"""

from functools import reduce

def get_coefficients(equation):
    """

    Returns the coefficients of the passed polynomial. If no coefficent, then 1 is returned.
    Only works for single digit coefficents, if present.

    :param equation: The equation to be analyzed

    """
    parts = equation.split()
    coeffs = []
    for part in parts:
        if part[0] == "x":
            coeffs.append(1)
        if part[0] == "-":
            coeffs.append(int(part[1]) * -1)
        if part[0] == "+" and "x" in part:
            if len(part) == 2:
                coeffs.append(1)
            else:
                coeffs.append(int(part[1]))
    return coeffs

def get_factors(equation):
    """
    Returns a list of factors of the constant

    :param n: Number to get factors from

    """

    constant = int(equation[len(equation) - 1])

    ###########################################
    """
    ===========================================
    Equation from StackOverflow user @agf
    https://stackoverflow.com/a/6800214/8968906
    ===========================================
    """
    factors = list(
        set(
            reduce(
                list.__add__, (
                    [i, constant//i] for i in range(1, int(constant**0.5) + 1) if constant % i == 0
                )
            )
        )
    )
    ###########################################

    #Add negatives
    length = len(factors)
    for i in range(length):
        factors.append(-factors[i])
    return factors

def synthetic_division(coefficients, factors):
    """
    Performs synthetic division with the passed coefficients and factors
    Returns a list of intercepts

    :param coefficients: Coefficients to use in the calculation
    :param factors: Factors to test

    """

    coeffs = coefficients
    facs = factors
    ints = []

    for fac in facs:
        current_sum = 0
        for coeff in coeffs:
            current_sum += coeff
            current_sum *= fac
        if current_sum == 0:
            ints.append(fac)

    return ints


def main(equation):
    """

    Gathers the coefficients, factors and intercepts from the equation

    :param equation: The polynomial to be solved

    """
    coefficients = get_coefficients(equation)
    constant = int(equation[len(equation) - 1])
    coefficients.append(constant)

    factors = get_factors(equation)
    intercepts = synthetic_division(coefficients, factors)

    return intercepts

if __name__ == '__main__':
    EQUATION = "x^3 -4x^2 +1x +6"
    print(f"X = {main(EQUATION)}")

Answer 1

Currently some of your code is very specialized to the exact use case you have. For example, the get_factors function takes the unparsed equation and needs to extract the constant itself. It would be a lot better if it just took a number and the parsing happens elsewhere. This way if you improve the parsing (to include multi-digit numbers, etc), you don't need to change the get_factors function.

At the same time, that function is borderline unreadable. It is also not the most efficient. Consider this alternative, which is shorter in lines of code, IMO way easier to read, and about two times faster:

def get_factors_of_constant(equation):
    c = int(equation[-1])
    factors = set()
    for i in range(1, int(c**0.5) + 1):
        if c % i == 0:
            factors.update([i, c // i, -i, -c // i])
    return list(factors)

---

For a better parsing, consider the output of the following regex:

import re

equation = 'x^3 -4x^2 +1x +6'
print(re.findall(r'\s?([\+\-]?\s?\d*)?(x)?\^?(\d*)?', equation))
# [('', 'x', '3'), ('-4', 'x', '2'), ('+1', 'x', ''), ('+6', '', ''), ('', '', '')]

It produces tuples of coefficients, whether or not there is an x and exponents. If the coefficient is empty, a 1 is assumed, if the exponent is empty, it is either a 1 or a 0, depending on if there is an x, and if all three are empty, you can skip it.

def parse(equation):
    coefficients, exponents = [], []
    matches = re.findall(r'\s?([\+\-]?\s?\d*)?(x)?\^?(\d*)?', equation)
    for coefficient, x, exponent in matches:
        if coefficient == x == exponent == "":
            continue
        coefficients.append(coefficient.replace(" ", "") or "1")
        exponents.append(exponent or "1" if x else "0")
    coefficients = list(map(int, coefficients))
    exponents = list(map(int, exponents))
    return coefficients, exponents

print(parse(equation))
# ([1, -4, 1, 6], [3, 2, 1, 0])

This can also parse multi-digits and deals both with missing parts (since you have the info on the exponent) and additional whitespace between number and sign:

parse("x^3 - 10x + 2")
# ([1, -10, 2], [3, 1, 0])
parse("x")
# ([1], [1])

It is also not perfect, for example it fails in this case:

parse("-x^2")
# ValueError: invalid literal for int() with base 10: '-'

You would need to add some special cases to the function for it to cover all edge cases, but it should be a good starting point.

Answer 2

Bugs

        if part[0] == "-":
            coeffs.append(int(part[1]) * -1)

Nowhere in the restrictions does it say that -x^2 is not a valid monomial. (It's not constant, and it doesn't have more than one digit of coefficient). But it isn't handled correctly.

---

x^2 -2x +1 gives output [1]. We'd expect the same output for 2x^2 -4x +2, but that gives output []. The coefficients are still single digits, and the constant term is still positive, so again this meets all of the documented restrictions.

---

Documentation

def get_factors(equation):
    """
    Returns a list of factors of the constant

    :param n: Number to get factors from

    """

There's no parameter n. Now, it would be better to take an integer n and factor that, because that is a very reusable function, whereas a function which takes an equation and factors its constant term has almost no reuse value.

---

def synthetic_division(coefficients, factors):
    """
    Performs synthetic division with the passed coefficients and factors
    Returns a list of intercepts

    :param coefficients: Coefficients to use in the calculation
    :param factors: Factors to test

    """

This is a classic example of documentation which tells me virtually nothing that I can't already see in the signature. The only useful line there is the one which tells me what it returns, and even there it's either unspecific or inaccurate: specifically, it returns (or, I assume the intention is that it should return) a list containing all the integer roots.

What I would find more useful from the documentation is

1. A reference to explain what synthetic division is.
2. A statement that the coefficients are coefficients of an integer polynomial, and the endianness.
3. An explanation of what factors is. (I would be inclined to rename the variable to candidate_integer_roots).

And having arrived at that level of understanding, the name is an irrelevance: what matters is the effect of the function (filters candidate roots to identify the true ones), not the algorithm employed (which is, in any case, not a division at all: it's polynomial evaluation using Horner's method).

And given that this is Python, which has reasonally good functional programming support baked in, I would think it worthwhile to refactor into a function which tests a single candidate root, and then use a comprehension with that as a filter in main.