11
\$\begingroup\$

I have a program I am writing that calculates Algebra 2 functions and equations. The interface is all CLI, and I even made commands that are similar to shell commands. That's not the part I want review on, so in the interest of space I'm going to consolidate as much as possible. If you want to check out the full program so far, you can see it here.

Tonight, I added a class and a few methods that factors the quadratic formula. The methods are capable of factoring when the a term is 1, or greater than 1.

Here is the code relevant to the function:

class Factor(Formulas):

    #---------- factor quadratic equation

    def FactorQuad(self, aval, bval, cval):
        # if the a value is equal to 1, we can factor the standard way
        if aval == 1:
            common_factor = self.MultSum(bval, cval)
            if common_factor:
                print "(x + %s)" % common_factor[0]
                print "(x + %s)" % common_factor[1]
                return True
            else:
                return False

        # if the a value is greater than 1, we must factor by grouping
        else:
            multval = aval * cval
            common_factor = self.MultSum(bval, multval)

            group_one = [aval, common_factor[0]]
            group_two = [common_factor[1], cval]

            # abs() insures the gcd is not negative due to negative values
            # on the second terms of each group
            group_one_gcd = fractions.gcd(group_one[0], abs(group_one[1]))
            group_two_gcd = fractions.gcd(group_two[0], abs(group_two[1]))

            # this conditional makes sure not to ignore negative values
            # on the first terms of each group
            if group_one[0] < 0:
                group_one_gcd *= -1
            if group_two[0] < 0:
                group_two_gcd *= -1

            set_one = (group_one_gcd, group_two_gcd)
            set_two = (int(group_one[0] / group_one_gcd),
                        int(group_one[1] / group_one_gcd))

            print "(%sx + %s)(%sx + %s)" % (set_one[0], set_one[1],
                                            set_two[0], set_two[1])


    #---------- multsum method

    def MultSum(self, bval, cval):
        """Find the number that multiplies to c and adds to b

        This is used to factor terms in the quadratic equation
        """
        tries = 0
        common_factor = 0
        factor = abs(int(cval / 2))

        while not common_factor:
            # first part of condition makes sure factor doesn't cause zero division error
            if factor and cval % factor == 0 and (factor + (cval / factor)) == bval:
                common_factor = factor

            if tries > abs(cval * 2):
                print "Error: The quadratic equation is not factorable"
                return False

            factor -= 1
            tries += 1

        return (int(common_factor), int(cval / common_factor))

Brief explanation:

  • The Factor class inherits from the Formulas class which contains various basic calculations that can be used universally across functions and methods (reduce fractions, count significant figures, etc). In these methods shown here, none of the inheritance is used so I figured it was pointless to show the parent class.

  • The Factor class will soon contain factorization methods for other equations, but right now it is just the quadratic.

  • It contains two methods, one that factors the quadratic equation (FactorQuad) and one that finds the factors that multiply to the c value and add to the b value (MultSum for lack of a better name).

  • FactorQuad is separated into two parts - one if the a value of the quadratic is 1, which is fairly simple to calculate, and a second part if the a value is greater than 1, which requires factoring by grouping.

I am hoping to get two things out of this review post:

  • I'd love to hear feedback on my code formatting, clarity of comments, and overall "cleanness" of the code. I only recently started writing useful programs over 50 lines long and I know that "clean code" is essential to programming. I'm really interested to see how I could improve formatting, docstrings, and comments.

  • I would also like to know if there are simpler ways to calculate the factorization. My particular concern is in the MultSum method. I feel like there must be a quicker way than looping through and checking a condition in every loop, but I'm missing it. Also, although factoring by grouping is more complicated than the first type of factoring, it seems like it could be shorter.

\$\endgroup\$
  • \$\begingroup\$ Do you assume that a, b, and c are all positive integers? \$\endgroup\$ – 200_success Dec 5 '13 at 9:10
  • \$\begingroup\$ No @200_success it worked with negative integers despite the many bugs pointed out below \$\endgroup\$ – samrap Dec 5 '13 at 16:03
15
\$\begingroup\$

1. Bugs

  1. The code fails to factorize \$x^2 + 2x + 1\$:

    >>> Factor().FactorQuad(1, 2, 1)
    Error: The quadratic equation is not factorable
    False
    

    It should print the factorization (x + 1)(x + 1).

    This is caused by a bug in MultSum when cval is 1:

    >>> Factor().MultSum(2, 1)
    Error: The quadratic equation is not factorable
    False
    

    It should return the pair (1, 1). The problem here is that the loop starts at int(cval / 2), but when cval is 1 then this is 0 and so the factor 1 is never considered.

  2. The code fails to factorize \$x^2 + 2x\$:

    >>> Factor().FactorQuad(1, 2, 0)
    Error: The quadratic equation is not factorable
    False
    

    It should print the factorization x(x + 2).

    This is caused by a bug in MultSum when cval is 0:

    >>> Factor().MultSum(2, 0)
    Error: The quadratic equation is not factorable
    False
    

    It should return the pair (2, 0).

  3. The code raises TypeError if I ask it to factorize \$2x^2 + 2x + 1\$:

    >>> Factor().FactorQuad(2, 2, 1)
    Error: The quadratic equation is not factorable
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
      File "cr36689.py", line 21, in FactorQuad
        group_one = [aval, common_factor[0]]
    TypeError: 'bool' object has no attribute '__getitem__'
    

    That's because the function MultSum returns the exceptional value False if it fails. But FactorQuad neglects to check for this exceptional value.

    It is generally best in Python to handle exceptional cases by raising an exception, so in MultSum I would write:

    raise ValueError("Quadratic expression is not factorable.")
    

    This would avoid the need to handle the exceptional return value in FactorQuad.

2. Other comments

  1. The Factor class is unnecessary. In object-oriented programming, an object represents some thing and a class represents a group of things with similar behaviour.

    But an instance of the Factor class doesn't seem to be any kind of thing. It doesn't have any instance data. And the methods FactorQuad and MultSum make no essential use of self. You can see in the examples above that they all start by creating a Factor() object that is thrown away as soon as its method has been called. All this suggests that there is no need for the Factor class, and FactorQuad and MultSum could just be ordinary functions, not methods. (Most likely there is no need for the Formulas class either.)

    In some programming languages classes are also used as containers for functions. But in Python that's not necessary: you can collect functions into a module.

  2. The FactorQuad methods lacks a docstring. What does it do and how am I supposed to call it?

  3. Variables could be named a, b and c instead of aval, bval and cval.

  4. Instead of writing:

    int(cval / 2)
    

    make use of Python's floor division operator and write:

    cval // 2
    
  5. The docstring for MultSum says:

    Find the number that multiplies to c and adds to b
    

    but actually the method returns two numbers. The docstring needs to be something like this:

    Return a pair of integers (x, y) such that x+y = b and x*y = c.
    If there are no such integers, raise ValueError.
    
  6. The MultSum method loops over the numbers from abs(int(cval / 2)) downwards to abs(int(cval / 2)) - abs(cval * 2). The usual way to loop over numbers in a range in Python is to use the range function. Here you might write something like:

    c = abs(cval) // 2 + 1
    for factor in range(-c, c + 1):
        # ...
    
  7. If aval is 1, then FactorQuad prints the two factors on separate lines and returns True, otherwise it prints the two factors on the same line and returns None:

    >>> Factor().FactorQuad(1, 3, 2)
    (x + 1)
    (x + 2)
    True
    >>> Factor().FactorQuad(2, 3, 1)
    (1x + 1)(2x + 1)
    

    It would be better if the output were consistent in the two cases. Also, it would be nice to print (x + 1) instead of (1x + 1).

  8. If any of the roots is positive, the printed results look poor:

    >>> Factor().FactorQuad(1, -2, 1)
    (x + -1)
    (x + -1)
    True
    >>> Factor().FactorQuad(2, -3, 1)
    (2x + -1)(1x + -1)
    

    It would be nicer to print (x - 1) instead of (x + -1).

  9. If \$a\$, \$b\$ and \$c\$ have a common divisor, that divisor is not pulled out of the factorization. For example:

    >>> Factor().FactorQuad(2, 4, 2)
    (2x + 2)(1x + 1)
    

    It would be nicer to print 2(x + 1)(x + 1) here.

3. An alternative approach

I'm sure you're familiar with the quadratic formula: $$x = {−b ± \sqrt{b^2 − 4ac} \over 2a}$$

The expression \$b^2 − 4ac\$ (inside the square root) is known as the discriminant. If this is a perfect square, then the quadratic equation has rational root(s); if not, the equation cannot be solved over the rational numbers.

That suggests the following approach:

from math import sqrt
from fractions import Fraction, gcd

def factorize_quadratic(a, b, c):
    """Factorize the quadratic expression ax^2 + bx + c over the
    rational numbers and print the factorization. If this is not
    possible, raise ValueError.

        >>> factorize_quadratic(1, 3, 2)
        (x + 1)(x + 2)
        >>> factorize_quadratic(1, 3, 0)
        x(x + 3)
        >>> factorize_quadratic(2, -9, -5)
        (2x + 1)(x - 5)
        >>> factorize_quadratic(4, -12, 8)
        4(x - 1)(x - 2)
        >>> factorize_quadratic(1, -2, 1)
        (x - 1)^2
        >>> factorize_quadratic(5, 0, 0)
        5x^2
        >>> factorize_quadratic(1, 3, 1)
        Traceback (most recent call last):
          ...
        ValueError: No factorization over the rationals.

    """
    # Extract common factor, if any.
    f = abs(gcd(gcd(a, b), c))
    a, b, c = a // f, b // f, c // f

    # Is the discriminant a perfect square?
    discriminant = b * b - 4 * a * c
    root = int(sqrt(discriminant))
    if root * root != discriminant:
        raise ValueError("No factorization over the rationals.")

    # The two roots of the quadratic equation.
    r, s = Fraction(-b - root, 2 * a), Fraction(-b + root, 2 * a)

    # Sort the roots by absolute value. (This step is purely for
    # the readability of the printed output: the intention is that
    # we get "x(x + 1)" instead of "(x + 1)x", and "(x + 1)(x + 2)"
    # instead of "(x + 2)(x + 1)".)
    r, s = sorted((r, s), key=abs)

    # Self-test: check that the factorization is correct.
    assert(r.denominator * s.denominator == a)
    assert(r.denominator * s.numerator + r.numerator * s.denominator == -b)
    assert(r.numerator * s.numerator == c)

    def maybe(x):
        if x == -1: return '-'
        if x == 1: return ''
        return x

    def factor(r):
        if r == 0: return "x"
        n, d = r.numerator, r.denominator
        return "({}x {} {})".format(maybe(d), '-+'[n < 0], abs(n))

    if r == s:
        print("{}{}^2".format(maybe(f), factor(r)))
    else:
        print("{}{}{}".format(maybe(f), factor(r), factor(s)))

Note that the docstring for the function includes some example code. These examples can be executed using the doctest module.

\$\endgroup\$
  • \$\begingroup\$ Thank you for pointing out the bugs and I completely forgot about the quadratic formula, it's been two years since I took Algebra 1 and we haven't got to it yet in Alg2. Thanks! \$\endgroup\$ – samrap Dec 5 '13 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.