22C:30, 22C:115 Homework 1

Problem 1
The rational class discussed in class this week is contained in the following two files: rational.h and rational.cxx.

1. Add two accessor member functions to this class: ceiling() and floor(). If s is a rational object then the function call s.ceiling() should return the smallest integer greater than or equal to s. Similarly, the function call s.floor() should return the largest integer less than or equal to s.
2. Now overload the operators +, -, *, and / so that they each take two rational arguments and return a rational result. So for example, the signature of the function that overloads the + operator would be:

   rational operator +(const rational & left, const rational & right)
   

   Note that these functions are not member functions of the rational class.
3. Overload the insert operator << and the extract operator >> so that these operators can be used to input and output rational objects. Specifically, the if s is a rational object, then the statement cin >> s; should read input of the form:

   [white space] [an integer] [white space] / [white space] [an integer]
   

   and update s so that its numerator is the first integer in the input and its denominator is the second integer in the input. Similarly, the statement cout << s; should produce output of the form

   [numerator of s] / [denominator of s]
   

Problem 2
In class we discussed a greedy algorithm for the Egyptian fraction problem. Recall that this is the problem of expressing a given non-negative rational number as the sum of distinct unit fractions.

1. Implement the greedy algorithm for the Egyptian fraction problem in C++ making use of the rational class. Turn in a printout of your C++ implementation. Your implementation will be judged on how well you have used the rational class.
2. Use your implementation to pruduce a set of distinct unit fractions whose sum is 5/21. Report this set of unit fractions. Is it possible to express 5/21 as the sum of fewer distinct unit fractions? If so, report this smaller set distinct unit fractions that add up to 5/21.
3. As you run the greedy algorithm for the Egyptian fraction problem, sometimes the size of the denominator of the unit fractions grows quite quickly. For example, for 4/17, the greedy algorithm produces 1/5, 1/29, 1/1233, and 1/3039345 as the answer. This makes integer overflow a problem for our implementation.

   To solve this problem, I provide the interface and implementation of the BigInt class: bigint.h and bigint.cxx (downloaded from Owen Astrachan's website at Duke University). This class allows us to define and use integers with an arbitrary number of digits.

   Enhance the rational class further by defining the numerator and denominator of a rational as BigInt objects, rather than as int variables. It is possible that you might have to make other changes to the rational class so that it works correctly with BigInt objects. Submit a printout of your new rational class. Also, use your new rational class to report a set of distinct unit fractions that add up to 4/3889.