Project 3: Fractions

CSE 143
Summer 1998

For this assignment, you will implement a Fraction class and a client using that class. A Fraction represents the ratio of an int and a non-zero int. Fractions will support the following operations: addition, subtraction, multiplication, division, negation, test for equality, printing to an ostream, conversion to a C++ double, and arbitrary-precision decimal expansion. In addition to representing rational values, the Fraction class must also represent the exceptional values Inf (infinity), -Inf (negative infinity), and NaN (not a number). The client is a simple calculator that keeps its results as a fraction rather than as a floating point number.

Operations on fractions

In the above table, '*' as an Op value means any value, 'i' represents any positive, non-exceptional value, and -i represents any negative, non-exceptional value.

Overflow: Because the Fraction class represents the ratio of 2 C++ ints, it is possible to manipulate Fractions in such a way as to produce a value which cannot be represented by two C++ ints. More disturbingly, badly-organized code may result in an overflow during an intermediate step even though the final result could be represented as the ratio of two ints. Ideally, you would like to structure your code to eliminate or at least reduce occurences of integer overflow. The following is a list, from simplest (least robust) to most complex (most robust), of ways to deal with this problem.

• Ignore the problem. When arithmetic overflow occurs, the Fraction class does not notice or care.
• Try to avoid the problem. You still do not detect overflow, but you structure your code in such a way as to avoid it. For example, the straighforward method of multiplying 9999999/2000000 by 1000000/3333333 might produce an overflow, but by correctly structuring your code, you can get the correct answer of 3/2.
• Detect the problem. Rather than using the arithmetic operators in the language which might overflow, write your own functions for addition, multiplication, or anything else you need, that signal when an overflow has occured. When overflow occurs, return NaN rather than the unpredictable value either of the above approaches returns
• Try and avoid the problem (as above), but detect it if it occurs (as above)

A caveat: it is possible to have a Fraction such that overflow occurs in the call to expand. This happens in the sample executable we have provided, and it is acceptable to do what we do (have expand return false if overflow occurs in the expansion process). However, it is possible to correctly expand these Fractions to the specified precision using a more complicated method of long division; you will receive extra credit if you do this, but you should do so only after the rest of your code is correctly completed (see our suggested approach below)

Moving down this list by writing more elaborate checks will earn you more credit; however, this assignment is not about solving the problem of overflow. Simply stopping after the first step ("ignore the problem") will earn you almost full credit. Please do not attempt to solve the more complex problems related to overflow until you have finished the rest of the assignment. See the "Suggested Approach" section of the homework for more information.

Note that to handle overflow, you'll find the header file limits.h very useful. It defines two extremely important constants: INT_MAX, the largest possible value an int can have, and INT_MIN, the smallest value an int can have. limits.h is defined in the C++ standard library, just like iostream.h.

The client

The client for the Fraction class is a simple calculator that operates on rational numbers. When run, the calculator displays the current value it is computing (which defaults to NaN). The user can enter any of the following commands, followed by the Enter key.

<number>

Set the current value to be <number>.

-

Negate the current value.

d

Display the current value as represented by a C++ double.

e

Display the current value as a decimal value expanded to a string of length 80 (be careful to maintain your discipline and avoid "magic numbers" in your code).

<op> <number>

Set value to (value <op> <number>). The whitespace between <op> and <number> is optional.

In the above list, <number> is either a string of digits, or a fraction composed of a string of digits followed by the character '/' followed by another string of digits. Hence, "1" and "1/2" are valid numbers, but "1/" is not. You don't need to worry about what happens if either string of digits is too big to fit in an int until you get to handling overflow. Notice that number cannot be negative; this is for simplicity. If you want to subtract -3, you have to add 3. If you want to divide by -3, you have to divide by 3 and negate the result separately.

Any line that does not fit one of the above descriptions should give the message "incomprehensible line ignored", and should not change the current value.

After each command is interpreted, the new value (which might be the same as the old value, e.g. when the line is not understood) should be displayed, and then the client waits for another command.

Also, <op> represents one of '+', '-', '*', and '/'.

Detailed Specification

Program organization: Your project will consist of 5 or 7 files.

Two files are supplied in their final form, and cannot be changed:

• gcd.cpp: code to calculate the greatest common divisor of two integers. you should use this to reduce your Fractions to lowest terms: the lowest terms form of a/b is (a/gcd(a, b))/(b/gcd(a, b)).
• gcd.h: header file for gcd.cpp

Two files have been given and should be modified as specified:

• fraction.h: the header file for the Fraction class. The existing public portion of the class should not be changed, but you may add private members, define relevant constants, etc. in this file. If you wish, you can also try experimenting with other public member functions that perform interesting operations on Fractions. But such experimentation is purely optional and will not be graded.
• fraction.cpp: the implementation file for the Fraction class. We have given you the implementation of operator<< which takes a Fraction in this file; you should implement the remaining functions here. We have given a dummy implementation of expand as well; this is because our suggested implementation approach (outlined below) recommends implementing this function towards the end.

The following file is not supplied and should be written by you:

• calc.cpp: the client.

The following files are optional, and relate to the correct handling of arithmetic overflow in your Fraction implementation. If you choose to handle overflow, put any functions you create related to this task in these two files.

• safeops.cpp: code you provide to detect overflow when performing operations on Fractions. For instance, you may want to define a function that adds two integers only if their sum wouldn't overflow.
• safeops.h: header file for safeops.cpp.

Suggested Approach

We suggest you approach this assignment by breaking it down into the following pieces:

1. Implement the Fraction class in a straightforward manner. Do not worry about the exceptional cases, or about what happens if two Fractions can each be represented as the ratio of two C++ ints, but their product/sum/whatever cannot. Do not implement Fraction::expand at this time. Test your implementation by writing a simple driver that creates a few Fractions, performs operations on them, and prints out the results. Use our sample executable to compare your answers with ours.
2. Add in handling of exceptional cases (Inf, -Inf, NaN, dividing by zero, etc.). Test the special cases to verify that your answers match those in the table above.
3. Implement the client. Compare your client with the sample executable we have given you.
4. Implement the expand function, replacing our dummy implementation.
5. Handle overflow in the arithmetic operations.
6. Eliminate overflow in the expand function (this should be absolutely positively the last thing you implement, and is for extra credit only!)

Executable

Turn-In

When you're finished writing your solution, you can use the electronic turn-in form to submit it. Follow the instructions on that form (especially with regards to file naming conventions), print the receipt, and submit the receipt at the start of section, Tuesday, July 21st, 1998. For full credit, you must turn in electronically, print the receipt, and hand in that receipt in your section. You may also be able to drop your receipt in the drop box located on the first floor of Sieg hall, across from room 127. More details on this will follow.

If You Get Stuck

If you're struggling because you're having trouble expressing things in C++, you may want to try out some of the useful tips I provided. Although you don't need any of these to do well on the assignment, they are ideas that can simplify a lot of potentially ugly code.

If you need help with the lab environment or the online resources, go talk to a consultant in the IPL.

If you can't make progress in the actual assignment, please talk to the instructor or a TA. They are available during posted office hours, and sometimes by appointment. They will also occasionally help you out over email. You are invited to seek help from any available TA, not just your own.

You can discuss the assignment in general terms with other students. You can ask general questions on the student discussion list for this course, cse143@cs. But any code you write must be your own. For more details about what is and is not allowed, see the Software hygiene page.