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 non-integer 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 num; int den; }

typedef struct { int num; int den; } Rational;

Rational a, b, c;
a = RATinit(1, 3);
b = RATinit(1, 4);
c = RATadd(a, b);
RATshow(c);

Step 0.  Copy the file RAT.h that contains the following code:

typedef struct { int num; int den; } Rational;
Rational RATinit(int numerator, int denominator);
    void RATshow(Rational r);
Rational RATadd(Rational r1, Rational r2);
Rational RATmul(Rational r1, Rational r2);

Step 1.  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"

Step 2.  Write a program named e.c that uses your package to compute a rational approximation to e, using the Taylor series expansion e = 1/0! + 1/1! + 1/2! +1/3! + 1/4! + 1/5! + . . .   Print out the value that you get after each term is added to the approximation. Read in an integer n from standard input using scanf(), and print the first n approximations. The output for n = 6 is:

1/1  2/1  5/2  32/12  780/288  93888/34560

Step 3.  Develop an improved implementation ratbetter.c that staves off overflow longer. A trivial way to do this would be to use long int, but that is less helpful than you might think, so we consider algorithmic improvements.

A straightforward implementation of the rational arithmetic interface has two flaws that will jump out at you as you add terms to the list above to get more accurate approximations. You can't avoid overflow, but you can stave it off by exercising sound judgment. For example, in the fourth term in the example above, 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, but either ac or bd might overflow before the reduction, even though the reduced answer might represent no problem (e.g., 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 (e.g., 7/20 + 7/30 = 1/12 would create intermediate values as big as 600).

Submission.  Be sure to carefully explain the approach that you use to stave off overflow in your readme file. Note that you shall not change the interface or client at all: they can use either implementation. However, presumably the client will get more accurate answers with the improved implementation. As usual, turn in your code and your documentation with the command

submit126 3 readme rat.c e.c ratbetter.c

Extra Credit.  Write a client program that computes rational approximations to π, using the identities π / 4 = arctan(1) and the continued fraction expansion arctan(x) = x/(1 + (x^2)/(3 + ((2x)^2)/(5 + ((3x)^2)/(7 + ...)))) to compute rational approximations to the arctangent.

This is an extensively modified version of an assignment originally developed by A. LaPaugh and S. Arora.