How do you reduce a fraction in python?

The fractions module can do that

>>> from fractions import Fraction
>>> Fraction[98, 42]
Fraction[7, 3]

There's a recipe over here for a numpy gcd. Which you could then use to divide your fraction

>>> def numpy_gcd[a, b]:
...     a, b = np.broadcast_arrays[a, b]
...     a = a.copy[]
...     b = b.copy[]
...     pos = np.nonzero[b][0]
...     while len[pos] > 0:
...         b2 = b[pos]
...         a[pos], b[pos] = b2, a[pos] % b2
...         pos = pos[b[pos]!=0]
...     return a
... 
>>> numpy_gcd[np.array[[98]], np.array[[42]]]
array[[14]]
>>> 98/14, 42/14
[7, 3]

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 //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]

Input : x = 16, y = 10
Output : x = 8, y = 5

Input : x = 10, y = 8
Output : x = 5, y = 4

x = 8, y = 5

Can Python handle fractions?

How do you get a fraction in Python?