COS 126Rational Arithmetic |
Programming Assignment 3Due: 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:

represents the rationalstruct { int p; int q; }

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:typedef struct { int p; int q; } Rational;

In this assignment, you will learn an important general method for implementing and using new data types and their associated functions.int x, y; Rational a, b; a = RATinit(1, 3); b = RATadd(a, RATinit(1, 4)); x = b.p; y = b.q;

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

This file is called antypedef struct { int p; int q; } Rational; Rational RATinit(int, int); void RATshow(Rational); Rational RATadd(Rational, Rational); Rational RATmul(Rational, Rational);

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:

This gives your function implementations access to the#include "RAT.h"

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

In the present context we are interested in this program as an example of a1/1 2/1 5/2 32/12

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