# CS 21: Algorithmic Problem Solving

## HW #9: Writing a Fraction Class

Due 11:59pm Tuesday, April 10

The program handin21 will only submit files in the cs21/homework/9 directory.

Some of the problems will have optional components that allow you to further practice your skills in Python. Optional portions will not be graded, but may be interesting for those wanting some extra challenges.

A Fraction Class
Write a class that stores a fraction as an integer numerator and a non-zero denominator and supports basic operations on fractions such as add, subtract, multiply, and divide. In case you forgot how to work with fractions, Wikipedia has a quick refresher.

Below is a sample test program that shows how to create a new instance of the Fraction class and work with fractions.

``` def test():
f1=Fraction(1, 2)
f2=Fraction(1, 3)
f3=Fraction(2 ,4)
print "f1 =", f1
print "f2 =", f2
print "f1 times f2 =",f1.mul(f2)
print "f1 divided by f2=", f1.div(f2)
print "f1 minus f2=",f1.sub(f2)
print "inverse of f1=",f1.inverse()
print "negation of f1=",f1.neg()
print "negation of negation of f1=",f1.neg().neg()
print "decimal value of f2=",f2.float()

if f1 > f2:
print "%s is greater than %s" % (f1, f2)

if f3==f1:
print "%s equals %s" % (f3, f1)

try:
f3=Fraction(4, 0)
except ZeroDivisionError:
print "Creating a fraction with a 0 denominator is illegal"
```

The output of running this test code is

```f1 = 1/2
f2 = 1/3
f1 plus f2 = 5/6
f1 times f2 = 1/6
f1 divided by f2= 3/2
f1 minus f2= 1/6
inverse of f1= 2
negation of f1= -1/2
negation of negation of f1= 1/2
decimal value of f2= 0.333333333333
1/2 is greater than 1/3
1/2 equals 1/2
Creating a fraction with a 0 denominator is illegal
```

Your Fraction class must implement the following features:

1. Implement the class methods add, sub, mul, div, inverse, and neg. Each of these methods returns a new Fraction instance.
2. Implement a square method that squares an instance of a Fraction object and returns the new Fraction.
3. Implement the method float that returns a float representing the decimal equivalent of a fraction instance.
4. Implement the __str__ method to support printing of Fractions as strings. See the note regarding reduced fractions below.
5. Implement the __cmp__ method to support comparisions of two Fractions, as shown in the sample code above. Statements such as
```cmp(f1, f2)
f1 < f2
f1 >= f2
```
are valid comparisions in a correct implementation.
6. If the user tries to create a fraction with a 0 denominator, your class should raise an exception. What type of exception is raised by python when you try to divide by 0? The keyword raise in python will raise an exception of a particular type. An example is raise KeyboardInterrupt.
7. Document your class methods so that users who wish to use your class can figure out how to use it by running help(fraction).
8. Expand on the test() function above to test your class and verify that it works correctly.

Save your class implementation in the file fraction.py

Reduced Fractions
All of your fractions should be printed in reduced form, meaning that there is no integer greater than 1 that divides both the numerator and denominator of of your fraction. For example, 1/2 is the reduced form of the fraction 6/12. To get your fractions in reduced form, you may want to use the following algorithm to compute the greatest common divisor of two integers a and b.
```gcd(a, b) =
a               : if b=0
gcd(b, a mod b) : otherwise
```

If the denominator of any fraction is 1, you do not need to print the denominator when you display the fraction as a string. Thus 3/1 should be printed as just 3.

Supporting +, -, /, and * operators
When adding two integers a and b we write a+b instead of a.add(b). We can support similar notation for our Fraction class if we modify our class methods names to appropriate names that python interprets in a special way. Note that __init__ and __str__ are two example of such names. Simply change the name of your method add above to __add__ and then f1+f2 will be intepreted the same as calling the function f1.__add__(f2). Change the names for sub, mul, div, and float to include the underscores. If you are unsure about the names, use help(int) to determine the names for various math operations. Check that statements such as
```f1 + f2
f1 *= f3
f4 = -f5
float(f3)
```
work as expected.
Optional Extensions
As noted above, these questions are NOT required to receive full credit. There are several extensions you could add to this program. Here are a few we thought might be interesting.

Suppose we want to add 2 and 3/4. Currently we must represent 2 as a fraction 2/1 and then add the two fractions. Modify your addition function and other functions so that the can accept both integers and fractions input. For example, the following expressions would be valid:
```f1 = 3/4
f1+Fraction(2, 1)   #returns 11/4
f1+2                #also returns 11/4
f1*8                #returns 6 as a Fraction
```
You can use the type function to check the type of a particular function parameter. For example:
```def myFunction(val):
if type(val)==int:
print "val is an integer, do integer stuff"
elif type(val)==str:
print "val is a string, do string stuff"
else:
print "assume val is a fraction"
```
What happens if you try to add an integer and a fraction with the fraction on the right side of the addition, e.g., 3+f1? Try implementing the __radd__ method inside your Fraction class and have it simply call your __add__ method. Implement similar methods for the other math operations.

### More fun with recursion

Note, this optional assignment is only tangentially related to the assigment and is somewhat weird. However, some might find it interesting.

In writing your class for fractions, you probably used standard integer operations such as +, -, *, and / to compute your answers. Python is way too nice in giving you all those built-in functions. All you really need are the following:

1. a function increment(n) that takes an integer n and returns n+1.
2. a function decrement(n) that takes an integer n and returns n-1.
3. a function isZero(n) that returns True if n equals 0 and False otherwise.
4. recursion
Given these functions and recursion you can build other functions. A function f can take as input an arbitrary number of integer parameters and call any previously defined function, check if any of the parameters are 0, or make a recursive call. This seems like a rather limited set of tools, but given only these tools, can you define the following functions on the set of non-negative integers? Don't worry about handling negative numbers.
```add(a,b) #returns the sum of integers a and b
multiply(a,b) #returns the product
power(a,b) #returns a raised to the power of b
sub(a,b) #returns a-b if b <= a and 0 otherwise
greaterThan(a,b) #returns True if b is greater than a
```
Remember, the first function you write can only call increment, decrement, or isZero and use recursion. You cannot use loops. You cannot check if a number is greater than 3. You cannot use +, -, * or other math operations. The only if statement you can write is if isZero(n) for some parameter n. The second function you write can use the first function you write in addition to the basic functions. Included below are the implementations of increment, decrement, and isZero. They are the only functions that are allowed to use +,-, and generic if statements
```def increment(n):
return n+1

def decrement(n):
#don't allow negative values of n
if n > 0:
return n-1
return 0

def isZero(n):
return n==0
```

How many function calls do you make to compute something simple like multiply(2,2)? Aren't you glad python let's you write 2*2 instead?