COS 126

Rational Arithmetic
Programming Assignment 3

Due: Wednesday, 11:59pm

Implement a rational arithmetic package and a client program that uses it to compute rational approximations to e. The purpose of this assignment is to learn about type definitions, packaging interfaces and implementations, separate compilation, and arithmetic overflow.

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. C approximates noninteger rational numbers using floats or doubles, but these types are imprecise representations. For this assignment, you will represent rational numbers with a C structure that comprises two integers:

struct { int p; int q; }
represents the rational p/q. When a C type is used repeatedly for representing another, more abstract, type, it's conventional to specify a new type name in a type definition as follows:
typedef struct { int p; int q; } Rational;
This directive allows us to use rational numbers in C programs in much the same way that we use other types, as in the following sample code:
int x, y;
Rational a, b;
a = RATinit(1, 3);
b = RATadd(a, RATinit(1, 4));
x = b.p; y = b.q;
In this assignment, you will learn an important general method for implementing and using new data types and their associated functions.

First, make a file named RAT.h that contains the following code:

typedef struct { int p; int q; } Rational;
Rational RATinit(int, int);
    void RATshow(Rational);
Rational RATadd(Rational, Rational);
Rational RATmul(Rational, Rational);
This file is called an interface. Its purpose is to precisely spell out what the data type is (the possible values of variables having the type and functions that manipulate such variables). In this case, we are saying that Rational numbers are pairs of integers, and that we will have functions for: initializing them; showing (printing) them; adding two of them and putting the result in a third; and multiplying two of them and putting the result in a third.

Second, make a file named RAT.c and write straightforward implementations of all the functions. The first line of this file should include the interface, as follows:

#include "RAT.h"
This gives your function implementations access to the Rational typedef, and provides a check that the functions that you write have the same types of arguments and return values as promised in the interface. This file is called the implementation of the data type.

Third, write a program named e.c that uses your package to compute a rational approximation to e, using the series expansion e = 1 + 1/1! + 1/2! +1/3! + 1/4! + 1/5! + 1/6! + ... Print out the value that you get after each term is added to the approximation. The first few terms are

1/1
2/1
5/2
32/12
In the present context we are interested in this program as an example of a client: a program that uses the data type, but is implemented separately. To use the package in e.c, put #include "RAT.h" as the first line. Then, you can use variables of type Rational and the functions that are declared in RAT.h in e.c. If you've done everything properly, RAT.c and e.c can even be compiled separately. However, the easiest way to debug is to compile them together using cc RAT.c e.c, then a.out as usual.

A straightforward implementation of the rational arithmetic interface is easy, but has two flaws that will jump out at you as you add terms to the list above to get more accurate approximations. First, in the fourth line in the example in the previous paragraph, both numerator and denominator are divisible by 4, so we would prefer to see the result 8/3 instead of 32/12. You can fix this problem with Euclid's algorithm (see Sedgewick, p. 191), using it to change your package to adhere to the convention that functions only returns rational numbers whose numerator and denominator are relatively prime. The second problem, which is more subtle, is overflow: The products formed by the rational arithmetic functions might overflow, which 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, and either ac or bd might overflow before the reduction, even though the reduced answer might represent no problem (for example, suppose that a and d are equal and huge). You can't avoid overflow, but you can stave it off by exercising sound judgement when you use Euclid's algorithm in the implementations of the rational arithmetic functions.

The fourth part of this assignment is to develop an improved implementation RATbetter.c that handles a wider class of rationals than the straightforward implementation. Explain the approach that you use in your readme file, and don't go overboard. Note that you do not have to change the interface and the client at all: they can use either implementation. However, presumably the client will get more accurate answers with the improved implementation. Set the client to print out the maximum number of terms that you can get without having overflow.

As usual, turn in your code and your documentation with the command

/u/cs126/bin/submit 3 readme RAT.h RAT.c e.c RATbetter.c
Extra Credit: Write a client program that computes rational approximations to pi, using the identity pi = 16×arctan(1/5) - 4×arctan(1/239) and the approximation arctan(x) = x - (x^3)/3 + (x^5)/5 - (x^7)/7 + (x^9)/9 ... to compute rational approximations to the arctangents.

This is an extensively modified version of an assignment originally developed by A. LaPaugh and S. Arora.
Copyright © 1997 R. Sedgewick