COS 126 Assignment 3 Checklist

Goals

Create a "library" (much like stdio.h) that allows a client program to perform arithmetic using rational numbers.

Learn to use the client, interface, implementation paradigm.

Learn to use structs.

Learn about computer algorithms, including Euclid's greatest common divisor algorithm, for arithmetic. You will see that arithmetic is not trivial!

Checking your work and hints

Step-by-step instructions for getting started and additional hints are available here.

Note: do not alter the interface RAT.h. When we grade your program, we will use our version of the file. It lists some interface functions that you are not required to implement: these were included for debugging, and to assist students doing the extra credit.

Use sample client program RATtest.c to test your code. It is available at ftp://ftp.cs.princeton.edu/pub/cs126/rat. To run RATtest.c, use a compilation command like one of the following:

gcc126 RATtest.c rat.c
gcc126 RATtest.c ratbetter.c

No overflow will occur with an ideal implementation of ratbetter.c. Here is the desired output.

Your client program e.c should read a single integer N from standard input, and print out the first N approximations to e. Print each term on its own line.

Submission and readme

Submit the following files via assignment submission system:

readme.txt rat.c ratbetter.c e.c pi.c

Do not use different file names or capitalization. Do not submit a.out or RAT.h. The file pi.c is for the extra credit part.

The readme.txt file should contain:

Name, precept number.

High level description of code. Be sure to provide a plain English description (i.e., not C code) of your "better" method for adding and multiplying rationals which staves off overflow.

Describe any serious problems you encountered. List whatever outside help that you received.

Give the most accurate approximation of e obtained from e.c with rat.c. Identify (by hand or computer) the last term that is not garbage resulting from overflow. Do the same with ratbetter.c.

For this assignment, you only need to point out in the readme file where the overflow occurs. It is possible to write code to detect for overflow, and warn the user. So, if you want practice writing more robust code, go ahead and try, but this is not required.

Here's a template readme file.

Extra Credit

There are many ways to compute pi, but the continued fraction expansion given in the course packet appears to be one of the simplest and most useful for getting a good rational approximation.

                        x
arctan(x) = ---------------------
                1      +    x^2
                        ----------
                        3  +  (2x)^2
                            ---------
                             5 + (3x)^2
                                --------
                                   ...

For the extra credit, you will probably want to implement some of the optional interface functions in RAT.h. However, you may not add your own.

Your program should take an integer n as input, and print out the first n approximations to pi using the above formula.

Enrichment Links

There are other ways to compute rational approximations to e and π. The following are accurate to an amazing 16 decimal places: e = 28245729/10391023, π = 245850922/78256779.

There are lots of interesting Web sites on π including computing the value of π and a history of π calculations.

Kevin Wayne