| COS 233 Rational Number Data Type |
Programming Assignment Due: Monday, Feb. 8th at 11:59 pm |
The purpose of this assignment is to get you back into Java programming and remind you how to create and use new data types (classes). Specifically, you will implement a rational number class and a client program that uses it to compute rational approximations to e.
Please get started early on this assignment, especially if you think you may have forgotten Java.
Developing a rational number data type. Rational numbers are numbers that can be represented as the ratio of two integers; i.e., any number p/q where p and q are integers is a rational number. Java approximates non-integer rational numbers using floats or doubles, but these types provide imprecise representations. For this assignment, you will represent rational numbers with a new Java class, Rational. This class should have the following constructor:
- public Rational(long numerator, long denominator)
- public Rational add(Rational b) : Add the Rational object b to the object and return a new Rational with the sum.
- public Rational multiply(Rational b) : Multiply the Rational object b with the object and return a new Rational with the product.
- public Rational subtract(Rational b) : Subtract the Rational object b from the object and return a new Rational with the difference.
- public Rational divide(Rational b) : Divide the object by the Rational object b and return a new Rational with the result.
- public Rational reciprocal(): Return the reciprocal of the rational.
- public Rational negate(): Return -1 times the stored rational.
- public String toString(): Return a string representation of the rational number. If the denominator is 1, print the numerator only.
You can think of this as the interface that you will use to interact with your rational number data type. Its purpose is to spell out precisely the possible values of variables having the type and methods that manipulate such variables. In this case, we are saying that Rational numbers are pairs of long integers, and that we will have functions for: initializing them; printing them; adding/multiplying/subtracting/dividing two of them and putting the result in a third; and negating/finding the reciprocal of one of them and putting the result in a new Rational.
Typical use of this class might go something like:
Rational b = new Rational(-1, 3);
Rational sum = a.add(b);
System.out.println(sum); // prints 1/3
System.out.println(a.negate()); // prints -2/3
First, you should implement this class in a Java file called Rational.java. Be consistent in your methods, and be sure that they follow the interface defined above. Take special care to think about how you will handle negative numbers and zero. Note that division by zero will result in a compiler error.
While working on the code for the class, create a client program called RationalClient.java. If you are confused by what "client" means, read back over section 2.2. In the main method, develop some simple examples to test the functionality of the Rational class.
Once you are convinced that your code is correct, write a method, public
Rational approx_e(int N), in your client program that uses the Taylor
series expansion:
to compute the first N terms of the rational approximation of e. If you are having trouble with the factorial, you could look back at section 2.3 on recursion; it is ok to use the code that you find there. Print out the value that you get after each term is added to the approximation. The output for N = 6 should be:
1/1 2/1 5/2 32/12 780/288 93888/34560.
Improving the rational Rational class. There are several problems with our implementation of the rational number class. As we attempt to compute more accurate approximation of e, e.g., N around 10, what happens to the values? The odd behavior you observe is the result of overflow. The compiler will not tell you when the numerator or denominator are beyond the range of integers that can be stored in a long, so you must always be careful when doing numerical calculations.
There a few relatively simple changes we can make to the Rational class to hold off overflow for several more terms of the approximation. First, notice that our rational numbers are not always stored in their simplest form. For example, in the fourth term in the example above, both numerator and denominator are divisible by 4, so we would prefer to store the result 8/3 instead of 32/12.
You can fix this problem by modifying the Rational class to only store and return rational numbers with numerator and denominator relatively prime. Add a method that implements Euclid's algorithm to compute the greatest common divisor of two numbers to the class, and use it to enforce this condition. Think about what type of method the greatest common divisor code should be in. You shouldn't have to change much code in Rational.java to make this work.
Once you have reimplemented the relevant methods in Rational.java, recompute the approximation of e. Did the approximation improve?
Remember that how Rational's methods are implemented does not matter to programs that use the Rational class (i.e., client programs) as long as the interface is maintained. This is an important benefit of modular and object oriented programming; client code is isolated from the details of the implementation. You shouldn't have to change anything in RationalClient.java.
Extra Credit. (Optional) Even if we store the rationals in reduced form, the products formed by the rational arithmetic functions might overflow. This leads to erroneous results, even if the result can be represented. For example, a/b × c/d is equal the reduced value of ac/bd, but either ac or bd might overflow before the reduction, even though the reduced answer might represent no problem. (The naive method for computing 20/33 × 77/50 = 14/15 would overflow a variable capable of storing only two digit integers.) Similarly, a/b + c/d is equal to the reduced value of (ad + bc)/bd, but either ad, bc, or bd might overflow before the reduction, even though the reduced answer might represent no problem. For example, 7/20 + 7/30 = 7/12 would create intermediate values as big as 600.
Write a class called RationalBetter that allows the calculation of rationals that can be represented but would result in overflow if the naive arithmetic methods are used. Be sure to explain your approach in comments and the readme.txt. Though it is a good idea, you may not use Java libraries like java.math.BigInteger. Even if you can't compeletly solve it, submit any improvements you make.
Deliverables. Rational.java, RationalClient.java, and optionally RationalBetter.java along with the readme.txt file.
Be sure to carefully answer the questions in the readme.txt file as your answers are graded. [Link to readme.txt template]
Do not forget to comment your code. No comments = Points off.
This assignment was adapted by Tony Capra from an assignment created by R. Sedgewick, A. LaPaugh, and S. Arora.
| Available from: | Tuesday, 2 February 2010, 09:00 AM |
| Due date: | Monday, 8 February 2010, 11:59 PM |
| Filename | Optional? | Description | |
|---|---|---|---|
| Rational.java | No | ||
| RationalClient.java | No | ||
| readme.txt | No | ||
| RationalBetter.java | Yes | Extra credit |