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

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(
[i, constant//i] for i in range(1, int(constant**0.5) + 1) if constant % i == 0
)
)
)
)
###########################################

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

• Your program prints an empty list for EQUATION = "x^2 +0x -1" – shouldn't the result be [-1, 1] ? – Martin R Aug 7 '19 at 6:26
• @MartinR Currently, one of the constraints is that the constant has to be positive, which explains why your equation didn't work. I will update the question to make it clearer what the constraints are. – Linny Aug 7 '19 at 6:31
• I see. The problem is that your get_coefficients function does not capture the constant coefficient. – Btw, is this really a “synthetic division”? If I understand your code correctly, you determine all factors of the constant coefficient and try each of them if it solves the equation. – Martin R Aug 7 '19 at 6:46
• @MartinR I append the constant to the end of the list of coefficients in the main method. – Linny Aug 7 '19 at 8:16
• Yes, that is the part which works only for positive (single-digit) constants. – Martin R Aug 7 '19 at 8:17

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.

• I'm not sure if 'x' is legal input (examples are a bit inconsistent with omitting the 1), but the code doesn't appear to handle it properly. – JAD Aug 20 '19 at 9:26
• @JAD I thought I could get away with not checking that x is also empty, but apparently I couldn't. Fixed. – Graipher Aug 20 '19 at 9:30

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.