Goals
Create a "library" (much like
stdio.h
) that allows a client program to perform arithmetic using rational numbers.
Learn to use structs.
Learn to use client, interface, implementation paradigm
Learn about computer algorithms, including Euclid's greatest common divisor algorithm, for basic arithmetic. You will see that it's not trivial!
Checklist
Use the submit command:
/u/cs126/bin/submit 3 readme RAT.h RAT.c RATbetter.c e.c
. Do not use different file names. Ask a lab TA how to create directories if you're unsure. Do not submit
a.out
.
readme
Name, precept number.
Description of problems encountered and high level description of code.
Detail any help that you received.
Be sure to include a plain English description of your "better" method for adding and multiplying rationals which staves off overflow.
Output of e.c with RAT.c.Print out 15 terms - indicate which terms are garbage created from overflow.
Output of e.c with RATbetter.c. Print out 15 terms - indicate which terms are garbage created from overflow.
RAT.h
Copy exactly.
/u/cs126/code/RAT.h
is the interface - it provides a list of the functions that your client program can use. Of course, you will have to implement these functions in
RAT.c
.
RAT.c
Implement naive versions of
RATadd
,
RATmul
,
RATshow
,
RATinit
. Do not reduce fractions or do anything fancy.
You can use the sample client program
RATtest.c
to test your implementation.
e.c
Use library of rational functions that you created to compute e using the Taylor expansion 1/0! + 1/1! + 1/2! + 1/3! + . . .
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).
It is possible to get 13 terms 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
; there is no way you can possibly store the denominator of the 15th term of e, since it would require too many digits.
RATbetter.c
RATbetter.c
replaces
RAT.c
, so use the naive version as a starting point.
Implement improved versions of
RATadd
,
RATmul
, and
RATinit
.
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
gcd
function.
Don't forget to improve
RATmul
, even if
e.c
doesn't really benefit from doing this - other client program (including RATtest.c) will.
Can use sample client program
RATtest.c
to test your code - with an ideal
RATbetter.c
implementation, no overflow will occur.
overflow
For this assignment, you only need to point out in the readme file where the overflow occurs.
It is not too difficult to write code to detect overflow and warn the user. So, if you want practice writing more robust code, go ahead and try.
pi.c
There are many ways to compute pi, but the continued fraction expansion given in the course packet appears to be the most useful for getting a good rational approximation.
arctan(x) = x --------------------- 1 + x^2 ---------- 3 + (2x)^2 --------- 5 + (3x)^2 -------- ...
compiling
Type "
lcc RAT.c e.c
" or "
lcc RATbetter.c e.c
" - the whole benefit of client, interface, implementation is that you don't need to change the client program e.c at all.
Enrichment Links
There are other ways to compute rational approximations to e and pi. The following are accurate to 16 digits: 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