Simplify a fraction

Question

I have been learning Python for a while (my first programming language) in my spare time. Since it's been 20 years since math class, and I didn't get very far with that, I just brushed up on pre-algebra and have started learning algebra. I decided to try and write some scripts/functions for what I have been learning, and below is my attempt at writing a script to simplify fractions.

In this script I first check if the fraction given contains a '0', a '1' or if the numerator == denominator. Failing those test, I move on to finding multiples to do the simplification.

A few things that I am wondering:

• Is the main function just too long? Should I have broken it into smaller functions?
• In the first if block in simplify_fraction() fraction the 'else' part ends with 'pass'. Wasn't sure what else to do there? Or if that is fine as is?
• Since I use the abs() function numerous times for numer and denom variable, would I have been better to make a variable out of it so that the calculation is only done once?
• Anything else that don't look so great, or could be done better!

Also, I am aware I could create a function for user_input and add error checking to that if the user puts in anything else other than an integer, but I am not concerning myself with that for now.

This script is designed to be run through the command line.

def neg_or_pos(numer, denom):
    if numer < 0 and denom > 0:
        return True
    elif numer > 0 and denom < 0:
        return True
    else:
        return False

def simplify_fraction(numer, denom):
    #assess if fraction is negative
    negative = neg_or_pos(numer, denom)
    simplified_statement = ("%d/%d is already at its most simplified state" 
                           % (numer, denom))

    #Following 'if' block establishes if numerator and/or denominator is 0,
    #if numerator and denominator are equal,
    #and if numerator or denominator == 1 and/or -1
    if denom == 0 and numer == 0:
        return "%d/%d = 0" % (numer, denom)
    elif denom == 0:
        return "Division by 0 - result 'undefined'"
    elif numer == 0:
        return "0/%d = 0" % denom
    elif abs(numer) == abs(denom) and negative == False:
        return "%d/%d = 1" % (numer, denom)
    elif abs(numer) == abs(denom) and negative == True:
        return "%d/%d = -1" % (numer, denom)
    elif abs(numer) == 1:
        return simplified_statement
    elif abs(denom) == 1 and negative == False:
        return "%d/%d = %d" % (numer, denom, abs(numer))
    elif abs(denom) == 1 and negative == True:
        return "%d/%d = -%d" % (numer, denom, abs(numer))
    else:
        pass

    #find all multiples for numerator and denominator, except 1
    numer_multiples = []
    for i in xrange(2, abs(numer)+1):
        if abs(numer) % i == 0:
            numer_multiples.append(i)
    denom_multiples = []
    for i in xrange(2, abs(denom)+1):
        if abs(denom) % i == 0:
            denom_multiples.append(i)

    shared = []
    #establish if both numerator and denominator are prime numbers
    if len(numer_multiples) == 1 and len(denom_multiples) == 1:
        return simplified_statement
    #if numerator greater than denominator, find greatest common multiple
    #for denominator and divide numerator and denomator by it
    elif abs(numer) > abs(denom):
        for i in denom_multiples:
            if i in numer_multiples:
                shared.append(i)
        if len(shared) == 0: #no common multiple
            return simplified_statement
        else:
            return "%d/%d is simplified to %d/%d" %(numer, denom,
                    numer / max(shared), denom / max(shared))
    #if denominator greater than numerator, find greatest common multiple
    #for numerator and divide numerator and denomator by it
    else:
        for i in numer_multiples:
            if i in denom_multiples:
                shared.append(i)
        if len(shared) == 0: #no common multiple
            return simplified_statement
        else:
            return "%d/%d is simplified to %d/%d" %(numer, denom,
                    numer / max(shared), denom / max(shared))

print simplify_fraction(int(raw_input("Type in numerator >")), 
                        int(raw_input("Type in numerator >")))

Answer 1

Correctness

Your function reduces 0/0 to 0, but the result should be "undefined" or "invalid".

Too many special cases

Your function distinguishes far too many cases. The process of simplifying a fraction can be reduced to the following 4 steps:

1. Check for invalid input (denominator is zero).
2. Remove a common factor from numerator and denominator.
3. Make the denominator positive (e.g. 5/-3 -> -5/3). (This step can also be omitted, see below.)
4. Finally check if the (reduced) denominator is equal to one (e.g. 4/1 --> 4).

All other checks (if numerator is zero, comparing absolute values, etc) are not necessary and automatically handled by the above algorithm.

Computing the "common factor"

Your method to compute the common factor of numerator and denominator is

• Create a list of all factors of the numerator (using a brute-force algorithm that checks each possible factor).
• Create a list of all factors of the denominator.
• Create a list of the common factors.
• Take the largest element of that list.

But you don't need all factors, only the largest common one. So it would be faster to start with the largest possible common factor and stop as soon a common factor is found. This would roughly look like:

#find greatest common divisor for numerator and denominator, except 1:
common_factor = 1
for i in xrange(min(abs(numer), abs(denom)), 1, -1):
    if numer % i == 0 and denom % i == 0:
         common_factor = i
         break

On my MacBook Pro, this reduces the time to simplify the fraction 12345678/87654321 already from about 10 seconds to 1 second.

But you can do much better. The Euclidean algorithm is a well-known, simple and fast algorithm to compute the greatest common divisor of integers, and it is easy to implement.

The reduces the time to simplify 12345678/87654321 to about 0.025 seconds.

Putting it all together:

There are probably many Python implementations of the Euclidean algorithm, I copied one from https://stackoverflow.com/a/11175154/1187415:

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

        Unless b==0, the result will have the same sign as b (so that when
        b is divided by it, the result comes out positive).
        """
    while b:
        a, b = b, a % b
    return a

As you can see, dividing the denominator by the common divisor gives a positive result, which means that step #3 it not necessary anymore. This also means that the fraction is already simplified exactly if the common divisor of numerator and denominator is equal to one.

So your main method reduces to

def simplify_fraction(numer, denom):

    if denom == 0:
        return "Division by 0 - result undefined"

    # Remove greatest common divisor:
    common_divisor = gcd(numer, denom)
    (reduced_num, reduced_den) = (numer / common_divisor, denom / common_divisor)
    # Note that reduced_den > 0 as documented in the gcd function.

    if reduced_den == 1:
        return "%d/%d is simplified to %d" % (numer, denom, reduced_num)
    elif common_divisor == 1:
        return "%d/%d is already at its most simplified state" % (numer, denom)
    else:
        return "%d/%d is simplified to %d/%d" % (numer, denom, reduced_num, reduced_den)

Answer 2

neg_or_pos is a terrible function name.

A function name should generally be a verb or a verbal phrase. And, even if you made it a predicate as is_neg_or_pos it should always return True, as the fraction surely is negative or positive.

By making it is_negative or is_positive, you make your code a lot clearer. I would not know what a True result from is_neg_or_pos meant without reading the source, and predicate methods are generally really straightforward.

Answer 3

Is the main function just too long? Should I have broken it into smaller functions?

It's kind of long but not overly so. The first thing I would look for is elimination of redundancies. For example, in the last section there's no need to compare abs(numer) > abs(denom) because you will end up with the same max(shared) in both cases. You can cut out a whole lot of code that way.

In the first if block in simplify_fraction() fraction the 'else' part ends with 'pass'. Wasn't sure what else to do there? Or if that is fine as is?

The else: clause is not required in Python. You can just delete that (and the pass) and the logic will be unchanged.

Since I use the abs() function numerous times for numer and denom variable, would I have been better to make a variable out of it so that the calculation is only done once?

Probably, yes.

Other things I noticed:

• You have tests like negative == True. There is no need to compare against True because negative is already True or False (a boolean value). For negative == False use not negative.

• The reduction of something like 15/5 would be 3/1, but the reduction of 3/1 would be just 3. An additional challenge would be to make the output always in the most simple form, particularly if that is an integer.

• Your call to simplify_fraction contains two raw_input function calls. (I assume the fact that they both ask for a numerator is a typo.) The point I'd like to make here is that while I'm pretty sure Python always evaluates function arguments left to right, this is definitely not true in all languages. I would write that line as something like the following, to make it unambiguous:

  num = int(raw_input("Type in numerator >"))
  den = int(raw_input("Type in denominator >"))
  print simplify_fraction(num, den)
  

Answer 4

If you have an idea about the number of decimal points, calling frac.limit_denominator() will do the job just well.