Part 0:  Preparation

  • Review the Lecture P4, and do the relevant reading in Sedgewick.

  • The Complex data type from Lecture P4 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/struct/.

  • 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

    • Part 1:   Naive implementation

    The file RAT.h is the interface. It lists the functions (and their prototypes) that your client program can use. The file RATtest.c is a sample client program that uses the interface 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 
    Rational 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: 
    gcc126 rat.c RATtest.c
    and execute, as usual, with "a.out". You should get the following output. Note that some of the terms overflow; you will fix this problem in Part 3.

    • Part 2:     Client

    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 will be severely penalized if you ignore this warning.

  • You may want to write a factorial function.

  • Don't be alarmed if your client program does not use RATmul().

  • To test your client, compile with the naive implementation rat.c with the command: 
    gcc126 rat.c e.c
    • Part 3:    Improved implementation

    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: 
    gcc126 ratbetter.c e.c
    Note that the client program does not change at all. This is the whole point of the client-interface-implementation paradigm. ratbetter.c replaces rat.c, so it is a good idea to use the naive version as a starting point.

  • Write a gcd() function that takes in two integers as input, and returns the greatest common divisor of the two inputs. Note that the function gcd() does not appear in RAT.h. This means that the client program is not supposed to use the gcd() function directly, although interface functions like RATadd() may still call it.

  • 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 most of the points on this part of the assignment, 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:

    111111111111
    1 = 
    		 + 
    		 + 
    		 + 
    		 + 
    		 + 
    		 + 
    		 + 
    		 + 
    		 + 
    		 + 
    		 + 
    67891014151820242830

    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.


    • Kevin Wayne