6
\$\begingroup\$

I have decided to create a program that can factor and solve quadratic expressions in micropython, where the standard library is limited, and i have no idea how to implement external modules onto it, so i had to bake this program from scratch.

The simple premise is, that it can factor and solve most quadratic expressions, and displays the solutions in ways to make it easier to check your solution.

I have documented part of the program to make it easier to understand what each part of the program does. I would like some advice on optimizing and making the program more efficient and compact, based on the idea of micropython.

# quadratic factorer, and solver
from math import sqrt


def is_integer(n):
    """
    checks if the float given is an integer
    True - float can be an integer
    False - float is not an integer
    """
    return int(n) == n
    

def gcd(*values):
    """
    finds the greatest common divisor of values
    and returns the absolute value of the divisor
    """
    x, *b = values
    for y in b:
        while y != 0:
            (x, y) = (y, x % y)
    return abs(x)


def isclose(a, b, tolerance):
    """
    checks whether the difference between the two values are smaller or equal to the tolerance
    return True - yes
    return False - no
    """
    return abs(a-b) <= tolerance


def fraction(a, factor=0, tolerance=0.01):
    """
    Uses brute force, to turn a float into a fraction
    if a is a whole number, then it is returned.
    if a is a float, then the closest possible fraction to tolerance level of difference
        and returns a fraction in string format.
    """
    while True:
        factor += 1
        a_rounded = int(round(a*factor))
        if isclose(a*factor, a_rounded, tolerance):
            break
    if factor == 1:
        return a_rounded
    else:
        return "{}/{}".format(a_rounded, factor)


def simplify_fraction(numer, denom):
    """
    simplifies a fraction, to a simpler form
    """
    if denom == 0:
        return None, None
    # Remove greatest common divisor:
    common_divisor = gcd(numer, denom)

    return numer // common_divisor, denom // common_divisor


def get_determinant(a, b, c):
    """
    returns the determinant of a polynomial ax^2 + bx + c
    """
    return b**2 - 4*a*c


def factors(n):
    """
    finds the factors of n, and returns a list of factors (unordered)
    """
    return list(set(x for tup in ([i, n//i] 
                for i in range(1, int(sqrt(n))+1) if n % i == 0) for x in tup))


def simplify_sqrt(n):
    """
    simplifies the n in sqrt(n)
    and turns it into a surd

    return values:
    (x, y) --> xsqrt(y)
    - x is the coefficient of the surd
    - y is the value remaining in the sqrt

    (0, y) --> sqrt(y)
    (y, 0) --> y
    """
    perfect_square = None
    float_to_int = lambda x: int(x) if is_integer(x) else x
    for factor in sorted(factors(n), reverse=True)[:-1]:
        if is_integer(sqrt(factor)):
            perfect_square = factor
            break

    if perfect_square == n:
        return (int(sqrt(perfect_square)), 0)

    elif perfect_square:
        factor1 = sqrt(perfect_square)
        factor2 = n / perfect_square
        return (float_to_int(factor1), float_to_int(factor2))

    else:
        return (0, n)


def format_tuple_to_sqrt(A, B): # Asqrt(B) 
    """
    turns a tuple from simplify_sqrt to an actual string representation.
    """
    if A == 0:
        A = ""
    elif B == 0:
        return str(A)
    return "{}sqrt({})".format(A, B)


def solve_completing_the_square(a, b, c): 
    """
    ( x +- ysqrt(B) )/z
    acquires the values of x, y, B, and z by reverse engineering the solutions
    and returns them
    """
    f = simplify_sqrt(get_determinant(a, b, c))
    g = gcd(f[0], 2*a, -b)
    # x, y, B, z
    return -b/g, [int(f[0]/g), f[1]], (2*a)/g # x, (h[0], h[1]), z


def format_complete_the_square_solutions(x, h, z):
    """
    h = (y, B) --> ysqrt(B)
    acquires the x, h, and z 
    and formats a proper string representation for the solution using complete the square

    if z is 1
    then no '/1' is shown.
    """
    # ( x +- h[0]sqrt(h[1]) )/z
    h[0] = 0 if h[0] == 1 else h[0]
    h = format_tuple_to_sqrt(*h)
    if z < 0:
        x, z = x*-1, z*-1

    sol1 = "( {} + {} )/{}".format(int(x), h, int(z))
    sol2 = "( {} - {} )/{}".format(int(x), h, int(z))
    if z == 1:
        return sol1[:-2], sol2[:-2]
    return sol1, sol2


def solve_quadratic_equation(a, b, c):
    """
    returns a tuple of solutions, if a polynomial abc, has atleast 1 solution, else returns None
    formula = (-b+-sqrt(b^2-4ac))/2a
    """
    # two solutions, or one solution
    if get_determinant(a, b, c) >= 0:
        return ( (-b+sqrt(get_determinant(a, b, c))) / (2*a), (-b-sqrt(get_determinant(a, b, c))) / (2*a)) # (x1, x2)
    # no solutions
    else:
        return None, None


def factor_quadratic_equation(a, b, c):
    """
    factors the quadratic polynomial a, b, c on multiple conditions
    support when
    1) c = 0
    2) b = 0 (if perfect square)
    3) a, b, c present
    4) complete the square is involved
    """
    get_sign = lambda x: "+" if x > 0 else "-" # set the sign based on x's value
    flip_sign_if_negative = lambda x, sign: -x if sign == '-' else x # switch the signs for formatting if sign == '-'
    float_to_int = lambda x: int(x) if is_integer(x) else x # only if the float is actually an integer like 3.0

    if a < 0:
        a, b, c = a/-1, b/-1, c/-1

    if c == 0: # factor by gcf 6x^2 - 2x
        gcf = gcd(a, b)
        a, b = a/gcf, b/gcf
        gcf = "" if gcf == 1 else gcf

        sign = get_sign(b)
        b = flip_sign_if_negative(b, sign)

        return "{}x({}x{}{})".format(float_to_int(gcf), fraction(a), sign, fraction(b))

    else: 
        denom = 2*a
        x1, x2 = solve_quadratic_equation(a, b, c)
        if x1 and x2:
            x1_numer, x2_numer = x1*denom, x2*denom
        else:
            x1_numer = x2_numer = None

        if (not x1 and not x2) or not (is_integer(x1_numer) and is_integer(x2_numer)) or not is_integer(denom): 
        # factor by completing the square 2(x+3) + 1
        # (x+p)^2 + q
            global completing_the_square
            completing_the_square = True

            if a != 1:
                a, b, c = a/a, b/a, c/a

            p = b/(2*a)
            q = c - (b**2)/(4*a)

            sign1 = get_sign(p)
            sign2 = get_sign(q)
            p = flip_sign_if_negative(p, sign1)
            q = flip_sign_if_negative(q, sign2)

            return "(x{}{})^2 {} {}".format(sign1, fraction(p), sign2, fraction(q))

        else: 
        # normal factoring (x+3)(x+3)
            x1_gcd, x2_gcd = gcd(x1_numer, denom), gcd(x2_numer, denom)
            x1_numer, x2_numer = -x1_numer/x1_gcd, -x2_numer/x2_gcd
            x1_denom, x2_denom = denom/x1_gcd, denom/x2_gcd
            gcf = gcd(a, b, c)*a/abs(a)

            sign1 = get_sign(x1_numer)
            sign2 = get_sign(x2_numer)
            x1_numer = flip_sign_if_negative(x1_numer, sign1)
            x2_numer = flip_sign_if_negative(x2_numer, sign2)

            return "{}({}x{}{})({}x{}{})".format(float_to_int(gcf) if gcf != 1 else "", fraction(x1_denom) if x1_denom != 1 else "", sign1, fraction(x1_numer), fraction(x2_denom) if x2_denom != 1 else "", sign2, fraction(x2_numer))



while True:
    completing_the_square = False
    a = float(input("insert a: "))
    b = float(input("insert b: "))
    c = float(input("insert c: "))
    factored_form = factor_quadratic_equation(a, b, c)
    solutions = solve_quadratic_equation(a, b, c)

    print(factored_form) if factored_form else print("No Factored Form")

    if solutions[0]:
        if completing_the_square:
            solution0_fraction, solution1_fraction \
                = format_complete_the_square_solutions(*solve_completing_the_square(a, b, c))

        else:
            solution0_fraction = "" if is_integer(solutions[0]) else fraction(solutions[0])
            solution1_fraction = "" if is_integer(solutions[1]) else fraction(solutions[1])

        solution1 = "x1 = {}".format(round(solutions[0], 5)) if solution0_fraction == "" else "x1 = {} or\n{}".format(round(solutions[0], 5), solution0_fraction)
        solution2 = "x2 = {}".format(round(solutions[1], 5)) if solution1_fraction == "" else "x2 = {} or\n{}".format(round(solutions[1], 5), solution1_fraction)

        print(solution1)
        print(solution2) if solutions[0] != solutions[1] else None

    else:
        print("No Solution")

    stop = input("'x' to stop: ")
    if stop == 'x':
        break
\$\endgroup\$
4
\$\begingroup\$

Is there any place in factor_quadratic_equation where the return value of flip_sign_if_negative(x,sign) is something other than the absolute value of x? If not, I would recommend using absolute value, since that's a familiar function already.

Why a/-1 rather than -a?

The simple parts are well documented (though most of them would be easy to understand even without documentation), but then there are complicated parts with little or no explanation. And I'm not convinced that you've given much thought to what you really want factor_quadratic_equation to do.

You've written a fairly complicated algorithm here. Have you tested it to see whether the results are what you expected?

I copied your functions into in Python 3.8.3 and tried some examples of my own.

factor_quadratic_equation(1,4,3) returned '(x+1)(x+3)'. That's good.

factor_quadratic_equation(0.5,2,1.5) returned '0.5(x+1)(x+3)'. Also good.

factor_quadratic_equation(0.125,0.5,0.375) returned '(x+2)^2 - 1'. What? Why isn't the answer '0.125(x+1)(x+3)'? How is '(x+2)^2 - 1' even considered the same polynomial as (1/8)x^2+(1/2)x+(3/8), let alone being considered a factorization of that polynomial?

I can understand that when a real quadratic has no zeros, and hence literally cannot be factored into real monomials, you might fall back to the vertex representation as a useful explanation, but this function seems all too eager to fall back to that representation for quadratics with zeros.

factor_quadratic_equation(1.33,1.2,0) returns
'1.1102230246251565e-15x(1197957500880552x+1080863910568919)'.
I suppose this has something to do with the inexact representations of 1.33 and 1.2 in IEEE 754, but it seems bizarre.

factor_quadratic_equation(133,120,0) produced a traceback, at the bottom of which was

ValueError: invalid literal for int() with base 10: ''

And yet factor_quadratic_equation(133/2,120/2,0) returns '0.5x(133x+120)', as one might expect.

factor_quadratic_equation(6,5,0) also produced a traceback.

What do you think the results should be in all these cases? I still have some questions about coding style, but I think correct behavior is an even higher priority.

\$\endgroup\$
  • \$\begingroup\$ i believe the results are accurate for the vertex form, and the result returned "'1.1102230246251565e-15x(1197957500880552x+1080863910568919)'" is a consequence of my fraction function being unable to find the proper fraction to represent the answer as. \$\endgroup\$ – Eren Yaegar Aug 23 '20 at 14:52
  • \$\begingroup\$ '(x+2)^2 - 1' is not accurate for 0.125x^2+0.5x+0.375. It has the same zeros but the wrong vertex: (-2,-1) when it should be (-2,-0.125). And the fact your fraction function is having trouble finding a good representation just means your fraction function performs poorly. Test the gcd function; it also shows this kind of behavior. \$\endgroup\$ – David K Aug 23 '20 at 14:57
  • \$\begingroup\$ i see, do you think finding the least common multiple which is an integer, would solve this issue? \$\endgroup\$ – Eren Yaegar Aug 23 '20 at 15:08
  • \$\begingroup\$ It might help, but notice how when we change factor_quadratic_equation(1.33,1.2,0) to factor_quadratic_equation(133,120,0) it breaks. \$\endgroup\$ – David K Aug 23 '20 at 15:11
  • \$\begingroup\$ To be honest I was surprised how well the gcd function worked for non-integer values. The % operator in python is more versatile than I realized. You learn something new every day! \$\endgroup\$ – David K Aug 23 '20 at 15:13
-1
\$\begingroup\$

Some of your comments are superfluous, try to express intent in code. Some of your comments also lie.

"checks if the float given is an integer" What if I didn't pass in a float, should you guard for it?

"False - float is not an integer" Read that again, that is just nonsense

"finds the greatest common divisor of values" maybe just call the function greatest_common_divisor and remove the comment

" return True - yes return False - no " Oh really?

"simplifies a fraction, to a simpler form" What simple form?

You call one function is_integer with snake case, but another isclose, why not is_close?

"turns a tuple from simplify_sqrt to an actual string representation." This comment leads be to believe that these functions has to be called in very specific order, in that case, should they instead be put in a class and private and only used by the internal algorithm? What is the public interface of your solver?

"if (not x1 and not x2) or not (is_integer(x1_numer) and is_integer(x2_numer)) or not is_integer(denom)" Could this be extracted into a function with a better, e.g. if should_factor_by_completing_square(...)

Could completing_the_square not be global and be returned in the response from factor_quadratic_equation ?

Could factor_quadratic_equation be split up into multiple functions, e.g. if should_factor_by_completing_square: factor_by_square(...) else normal_factoring(...)

return "{}({}x{}{})({}x{}{})".format(float_to_int(gcf) if gcf != 1 else "", fraction(x1_denom) if x1_denom != 1 else "", sign1, fraction(x1_numer), fraction(x2_denom) if x2_denom != 1 else "", sign2, fraction(x2_numer))

Way too long a line, split this up, what is happening?

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! Technically, this is not a terrible review, but there are things that could be improved. For example, instead of saying "Some of your comments are superfluous, try to express intent in code. Some of your comments also lie." it would be better to point the specific comments, explain (gently!) what could be improved and why, and perhaps suggest better ones. You might also want to read codereview.stackexchange.com/conduct \$\endgroup\$ – Edward Aug 22 '20 at 19:04
  • 3
    \$\begingroup\$ How is "False - float is not an integer" nonsense? \$\endgroup\$ – superb rain Aug 23 '20 at 1:02
  • 1
    \$\begingroup\$ Well that's nonsense. First, it's documented with "float given". So it's not for "any type" but for floats. Why would it always return false? Many floats are integers. They'll even tell you themselves if you ask them, for example (3.0).is_integer() tells you True (on normal Python, apparently not on micropython, otherwise they wouldn't need to reimplement it). \$\endgroup\$ – superb rain Aug 23 '20 at 12:05
  • 1
    \$\begingroup\$ yeah, i knew is_integer() existed, but sadly micropython does not support it. \$\endgroup\$ – Eren Yaegar Aug 23 '20 at 15:09
  • 1
    \$\begingroup\$ Integer-datatypes don't have a monopoly on the word integer. \$\endgroup\$ – superb rain Aug 23 '20 at 16:32

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.