Simplify a fraction

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:
return True
elif numer > 0 and denom 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

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:

• Check for invalid input (denominator is zero).

• Remove a common factor from numerator and denominator.

• Make the denominator positive (e.g. 5/-3 -> -5/3).

(This step can also be omitted, see below.)

• 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)

StackExchange Code Review Q#66450, answer score: 18