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!

    • Grading

    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.

  • rat.c:   5 points.

  • ratbetter.c:   5 points.

  • e.c:   5 points.

  • Submission, readme, and style: 5  points.

    • Checking your work and hints

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

  • Use sample client program RATtest.c to test your code. It is available in the directory /u/cs126/files/rat/. No overflow will occur with an ideal implementation. 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. The assignment waffles between saying to print N and N+1 terms, so we won't deduct if you choose to print out N+1 instead. You can also use the programs e126 and ebetter126 to help check your work.

    • Submission and readme

  • Use the following submit command. 
    submit126 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.)

  • 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.

    • 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 simples 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.

    • 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