## Fractions - part 2

To multiply two fractions, like `(1/2) * (3/4)`, we need to multiply the numerators together, do the same for the denominators, to get a new fraction. For example:

    1   3   3
    - * - = -
    2   4   8

Sometimes, when we multiply fractions, the result can be expressed in a simpler form. For example:

    2    11   22   1
    -- * -- = -- = -
    11   6    66   3

In this lesson, we will teach Python how to multiply two fractions, and also how to simplify the result.

### Multiplying two fractions

With the two fractions defined in the last section, try to do the following:

        print a*b

Try it! You will get an error message, as Python does not know what it means to have the symbol "`*`" between two objects of the class `Fraction`. To tell Python to understand that the using the symbol "`*`" between two fractions means that we want to multiply these two fractions, we use the private function `__mul__()`. Here's our new code:

      1 class Fraction(object):
      2     def __init__(self, numerator, denominator=1):
      3         self.num = numerator
      4         self.denom = denominator
      5
      6     def __str__(self):
      7         if self.denom == 1:
      8             return "(%s)"%self.num
      9         return "(%s/%s)"%(self.num, self.denom)
     10
     11     def __mul__(self, other):
     12         num = self.num * other.num
     13         denom = self.denom * other.denom
     14         return Fraction(num, denom)
     15
     16 #== testing area below===
     17
     18 if __name__ == "__main__":
     19     a = Fraction(1, 2)
     20     b = Fraction(3, 1)
     21     assert str(a) == "(1/2)"
     22     assert str(b) == "(3)"
     23     print a*b

First, I made some minor changes on lines 7, 8 and 22, so that the denominator is not shown when it is equal to 1. This is slighly different from the exercise I suggested in the last lesson, as I chose to keep the parentheses to indicate it was still a object of the class `Fraction` and not simply an integer.

Next, I told Python that, to multiply two fractions, you multiply the numerators together [line 12], do the same with the denominators [line 13], and that the result is a new `Fraction` object [line 14]. If you try to run this program, the result [from line 23] will be "`(3/2)`", which is what we want.

Now, let't turn the working print statement into an assert one [line 23], and add a new test [lines 24 and 25], as indicated below.

     16 #== testing area below===
     17
     18 if __name__ == "__main__":
     19     a = Fraction(1, 2)
     20     b = Fraction(3, 1)
     21     assert str(a) == "(1/2)"
     22     assert str(b) == "(3)"
     23     assert str(a*b) == "(3/2)"
     24     c = Fraction(1, 3)
     25     print b*c

If we run this program, we find that the output is "`(3/3)`" which we recognize as being the same as `1`; it would be nice if Python would do the same. To do that, we'll use an algorithm that was invented more than 2000 years ago!

### Euclid's algorithm

In 300 BC (that is 300 years before year 0), the Greek philosopher Euclid published a series of 13 books entitled Elements. Those books contained what was known at the time about mathematics and geometry. Among other things, an algorithm for finding the greatest common divisor (or greatest common factor) was included It is very likely that this algorithm had been known before Euclid was born; some people believe that it was first discovered some 2500 years ago! Guido van Rossum, the creator of Python, wrote a short function that implemented Euclid's algorithm:

    def gcd(a, b):
        '''gcd returns the greatest common divisor
           of given 2 integers.'''
        while b:
            a, b = b, a%b
        return a

I will not explain Euclid's algorithm here. This is left as an exercise for you. However, I will make use of it and define a new function to simplify the results.

    def simplify(a, b):
        '''divides two integers by their common factor.'''
        common_factor = gcd(a, b)
        a /= common_factor
        b /= common_factor
        return a, b

Now, here's the new class definition:

      1 def gcd(a, b):
      2     '''gcd returns the greatest common divisor
      3         of given 2 integers.'''
      4     while b:
      5         a, b = b, a%b
      6     return a
      7
      8 class Fraction(object):
      9     def __init__(self, numerator, denominator=1):
     10         num, denom = self.simplify(numerator, denominator)
     11         self.num = num
     12         self.denom = denom
     13
     14     def __str__(self):
     15         if self.denom == 1:
     16             return "(%s)"%self.num
     17         return "(%s/%s)"%(self.num, self.denom)
     18
     19     def __mul__(self, other):
     20         num = self.num * other.num
     21         denom = self.denom * other.denom
     22         num, denom = self.simplify(num, denom)
     23         return Fraction(num, denom)
     24
     25     def simplify(self, a, b):
     26         '''divides two integers by their common factor.'''
     27         common_factor = gcd(a, b)
     28         a /= common_factor
     29         b /= common_factor
     30         return a, b
     31
     32 #== testing area below===
     33
     34 if __name__ == "__main__":
     35     a = Fraction(1, 2)
     36     b = Fraction(3, 1)
     37     assert str(a) == "(1/2)"
     38     assert str(b) == "(3)"
     39     assert str(a*b) == "(3/2)"
     40     c = Fraction(1, 3)
     41     assert str(b*c) == "(1)"
     42     d = Fraction(5, 10)
     43     assert str(d) == "(1/2)"

In lines 1 to 6, we introduced our `gcd()` function. By putting it outside the class definition, we make it easilty available to other programmers if they import our file. Just to show the other alternative, we put the method `simplify()` inside the class definition, on lines 25 to 30. We use `simplify()` on line 22 and test it on lines 39, 40 and 41.

We also use `simplify()` when we initialise a new fraction, on line 10 [with other minor changes on line 11 and 12] so that the newly created fraction will always be in simplified form. This is tested on lines 42 and 43.

Look closely at the changes we made. Everything works correctly, but there is one line that we added that wasn't required as it makes Python try to calculate the same thing twice. Can you see which one? Try to find it, before moving on to the next lesson where we will divide fractions.