Synthetic division calculator 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



  Coefficients must only be one digit, if present


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


  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)}")
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.