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 basic arithmetic. You will see that it's not trivial!

Unix tip of the week

Turn on all of your compiler warning and error messages to help you debug your code. (If you downloaded our .emacs file last week, this will be automatic.) The command

gcc -Wall -W -O -pedantic -ansi hello.c

compiles the program hello.c as before. The "flags" -Wall and -W turn on many compiler warning messages that were previously muted. The flags -ansi and -pedantic help ensure that your program conforms to ANSI C - this will ensure that you can compile it with different compilers on different operating systems. The flag -O makes the compiler run some heuristics to find uninitialized variables.
Alternatively, on arizona you can use the command

/u/cs126/bin/gcc126 hello.c

If you ask a lab TA, they can include the directory /u/cs126/bin in your path, and then you will only have to type "gcc126 hello.c" or "submit 0 hello.c readme".

To print your code in the 101 lab in two columns, you can use the command

enscript -2Grh -Ppsr hello.c

Alternatively, if /u/cs126/bin is in your path, just type "enscript126 hello.c".

Part 0: Preparation (0 points)

Review lecture P5 and do the relevant reading in Sedgewick.

The Complex data type from Lecture P5 is quite similar to what you will need to do, so you may wish to use that code as a starting point. The files COMPLEX.h, complex.c, and complexclient.c are available in the directory /u/cs126/files/lecture/adt/.

Copy the following files from /u/cs126/files/rat/ to an empty directory:

RAT.h   RATtest.c

You may do this with the following command:

mkdir rat                       # make a new directory
chmod 700 rat                   # set permissions
cd rat                          # move to that directory
cp /u/cs126/files/rat/* .       # copy files

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 students doing the extra credit.

Part 1: Naive implementation (3 points)

The file RAT.h is the inteface. It lists the functions that your client program can use. The file RATtest.c is a sample client program that uses the inteface functions to perform rational arithmetic. Your first task is to write an implementation file RAT.c, that implements the functions described in RAT.h so that client programs like RATtest.c can use it as a black box.

Implement naive versions of RATadd, RATmul, RATshow, RATinit. Do not reduce fractions or do anything fancy. Start by writing RATshow and RATinit. You can test out your code using RATtest.c as described below. But before you can do this, you need to define RATadd and RATmul. For now, you can just fill in these functions with temporary placeholder code. For example, you might begin by writing RATadd as

Complex RATadd(Rational r1, Rational r2) {
   printf("calling RATadd.\n");
}

This will enable you to write one function at a time, and test it out before proceeding.

To test your implementation, jointly compile it with RATtest.c with the command:

gcc RAT.c RATtest.c

and execute, as usual, with:

a.out

You should get the following answer. Note that some of the terms overflow; you will fix this problem in Part 3.

Part 2: Client (3 points)

In this part you will write a client program e.c that computes a rational approximation to the mathematical constant e using the Taylor expansion e = 1/0! + 1/1! + 1/2! + 1/3! + . . .

Use the library of Rational interface functions to perform all operations. Do NOT access the data structure directly.

You may want to write a factorial function - a good opportunity to practice coding a recursive function. It can also be done with a traditional while or for loop.

To test your client, compile with the naive implementation RAT.c with the command:

gcc RAT.c e.c

Part 3: Improved implementation (3 points)

In this part you will write a better version of the RAT.c implementation that you wrote in Part 1. The goal here is to stave off overflow by being a bit more clever.

You will jointly compile the new implementation with a client program using the command:

gcc RATbetter.c e.c

Note that the client program does not change at all. This is the whole point of the client-inteface-implementation paradigm. RATbetter.c replaces RAT.c, so it is a good idea to use the naive version as a starting point.

Implement improved versions of RATadd, RATmul, and RATinit. Don't forget to improve RATmul, even if e.c doesn't benefit from doing this. To avoid overflow, at the very least you will want to reduce fractions by dividing the numerator and denominator by their greatest common divisors, e.g., 10/15 to 2/3. This is enough to get 9 of the 10 points on the assignment (assuming no other deductions), so if you've already spent an excessive amount of time, you can stop here.

In addition to reducing fractions, there are other techniques to avoid overflow. For example, the naive way to add 7/10 + 4/15 would be to find a common denominator 150, and then add 105/150 + 40/150 = 145/150 = 29/30. Note that each term in the result has two digits, but the intermediate number 150 would overflow a variable that could only store two digit numbers. Before you begin coding, do some arithmetic with fractions using pencil and paper and try to isolate the techniques you use to simplify fractions and avoid big numbers in your intermediate calculations. Some good examples are in the RATtest.c file. Also consider the following example:

	1		1		1		1		1		1		1		1		1		1		1		1
1 =		+		+		+		+		+		+		+		+		+		+		+
	6		7		8		9		10		14		15		18		20		24		28		30

Some people find it useful to write a least common multiple (a.k.a, least common denominator) function for use with RATadd - this can be accomplished using Euclid's greatest common divisor algorithm (and some pencil and paper experiments).

The order in which you do computations can have significant impact on overflow. A common misperception in C is that (a*b)/c = (a/c)*b where a, b, and c are integers (even if c evenly divides a). To see why not, suppose a = b = c = 1,000,000. Then, the first expression perform an intermediate computation that results in the integer a*b = 1,000,000,000,000 potentially causing overflow. The second expression staves off overflow in this example by first computing a/c = 1.

In e.c it is possible to get 13 terms without overflow using a well-written RATbetter.c implementation. The largest integer that can be stored as an int on the arizona machine flagstaff is 2,147,483,647: consequently there is no way you can possibly store the denominator of the 15th term of e, since it would require too many digits.

Use sample client program RATtest.c to test your code. No overflow will occur with an ideal implementation. Here is the desired output.

Submission and readme (1 point)

Use the following submit command.

/u/cs126/bin/submit 3 readme RAT.c RATbetter.c e.c pi.c

Do not use different file names or capitalization. Do not submit a.out or RAT.h. (Obviously, pi.c need only be submitted by students that did the extra credit.) Your client program e.c should read a single integer N from standard input, and print out the first N+1 approximations to e.

The readme 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 overflow and warn the user. So, if you want practice writing more robust code, go ahead and try, but this is not required.

Extra Credit (1 point)

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

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

Enrichment Links

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

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

Kevin Wayne