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 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:

represents the rational number with numeratorstruct { unsigned int num; unsigned int den; }

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 { unsigned int num; unsigned int den; } Rational;

In this assignment, you will learn an important general method for implementing and using new data types and their associated functions.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:

This file is called antypedef struct { unsigned int num; unsigned int den; } Rational; Rational RATinit(unsigned int numerator, unsigned 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:

This gives your function implementations access to the#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:

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

Now, you can use variables of type#include "RAT.h"

**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.
**Do not** change the interface file `RAT.h`.
Your client program `e.c` should work with either
implementation `rat.c` or `ratbetter.c`.
Presumably, `e.c` 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.*