COS 126Rational
Arithmetic |
Due: Wed. 3/5/97, 11:59pm |

For this assignment, you will implement a rational arithmetic packagea
set of functions that does arithmetic on a precise representation of rational
numbers. You'll write the functions `reduce`

, `add`

,
`minus`

, `multiply`

, and `divide`

in one
file, `rat.c`

. You'll also write a test program, `testrat.c`

,
that computes *x*^{2}/(*x* - 1) where *x* is a
rational number. The purpose of this assignment is to learn about type
definitions, packaging interfaces and implementations, using modules, and
arithmetic overflow.

Rational numbers are numbers that can be represented as the ratio of two
integers, i.e., any number *p/q* where *p* and *q* are
integers is a rational number. C represents noninteger rational numbers using
floats or doubles, but these types can't represent all rationals precisely. The
rational number package represents a rational number with a 2-element integer
array:

`int x[2];`

represents the rational `x[0]`

/`x[1]`

. When a C type
is used repeatedly for representing another, more abstract, type, it's
conventional to specify a new type name in a *type definition*. The
declaration

`typedef int Rational[2];`

declares Rational to be the type "`int [2]`

"a
2-element array of ints. Henceforth, rational numbers can be declared with
declarations like

`Rational x;`

here are many representations for each rational number. For example, 2/3 can
be represented as 2/3, 4/6, 18/27, and even 2*x*/3*x* for any
postive *x*. We'll use only the *reduced* representation for a
rational number: *p/q* is reduced if *q*>0 and the *greatest
common divisor* or *p* and *q* is 1. You'll need a function
that given an arbitrary *s/t*, computes the equivalent reduced *p/q*,
which can be done by computing the greatest common divisor, the "gcd",
of *s* and *t*.

Euclid's famous algorithm for computing the gcd of *s* and *t*
is based on the observation that, for positive *s* and *t* with
*s* <= *t*, the gcd of *s* and *t* is the
same as the gcd of *s* and *t-s*. This observation leads to the
following function for computing the gcd.

int gcd(int s, int t) { s = abs(s); t = abs(t); if (s > t) { int temp = s; s = t; t = temp; } while (s > 0) { t -= s; if (s > t) { int temp = s; s = t; t = temp; } } return t; }

`abs`

is the standard library function (declared in `stdlib.h`

)
that returns the absolute value of its argument. This algorithm is simple, but
there's an important improvement: When *t* is much larger than *s*,
Euclid's algorithm loops many times before finding the (relatively small) gcd.
Many of these iterations can be avoided by noticing that for positive *s*
and *t* with *s* <= *t* the gcd of *s* and
*t* is equal to the gcd of *s* and *t* mod *s*.

The rational arithmetic interface is specified in the header file /u/cs126/examples/rat.h. Here are the functions:

`extern void reduce(Rational z, int p, int q)`

- sets
`z`

to the reduced representation for`p/q`

. `extern void minus(Rational z, Rational y)`

- sets
`z`

to the reduced representation for`-y`

. In a negative Rational, the numerator is negative and the denominator is positive. `extern void add(Rational z, Rational x, Rational y)`

extern void multiply(Rational z, Rational x, Rational y)

extern void divide(Rational z, Rational x, Rational y- sets
`z`

to the reduced for, respectively,`x + y`

,`x * y`

, and`x / y`

.

Implement these functions in `rat.c`

. You'll need to include
`rat.h`

. You can copy
/u/cs126/examples/rat.h,
but don't change it. You can avoid copying
/u/cs126/examples/rat.h
by telling `lcc`

to find the include file in `/u/cs126/examples`

:

`%`

lcc -c -I/u/cs126/examples rat.c

Test your implementation by writing a program, `testrat.c`

,
that, for each of its rational number arguments *x*, computes *x*^{2}/(*x*
- 1), and prints the result and the intermediate values. For example,

%lcc -I/u/cs126/examples testrat.c rat.c%a.out 1/2 2/3 4/6 451/232(1/2)^2/(1/2 - 1) = (1/2)(1/2 / -1/2) = (1/2)(-1/1) = -1/2 (2/3)^2/(2/3 - 1) = (2/3)(2/3 / -1/3) = (2/3)(-2/1) = -4/3 (2/3)^2/(2/3 - 1) = (2/3)(2/3 / -1/3) = (2/3)(-2/1) = -4/3 (451/232)^2/(451/232 - 1) = (451/232)(451/232 / 219/232) = (451/232)(451/219) = 203401/50808

As the output in this example suggests, `testrat.c`

computes
*x*^{2}/(*x* - 1) by computing *x*(*x*/(*x*
- 1)). `testrat.c`

needs to include `rat.h`

, too, and is
thus an example of a "client," which is a program that uses a
general-purpose package, like `rat.c`

. `testrandom.c`

,
which includes `random.h`

, is another example of a client.

The straightforward implementation of the rational arithmetic interface is
easy, but has an important flaw, which is illustrated by
`/u/cs126/examples/area.c`

:

%lcc -I/u/cs126/examples /u/cs126/examples/area.c rat.c%a.out 30 40 50 1600 170030: area=899/1350 ~= 0.665926 40: area=533/800 ~= 0.66625 50: area=165886213/39465450 ~= 4.20333 1600: area=-1/0 ~= -Inf 1700: area=-7285019/9736072 ~= -0.74825

`area.c`

computes an estimate of the area under the curve *x*^{2} in the
interval -1 to 1 by summing the areas of *N* rectangular regions between
-1 and 1, where *N* is given by the program arguments. The correct
answer is 2/3; as shown above, area gets the right answer for small *N*,
but goes badly off the track for larger *N*. You don't have to
understand `area.c`

; just *use* it to test your rational
arithmetic functions.

The problem is *overflow*: The products formed by the rational
arithmetic functions might overflow, which leads to erroneous results, even if
the result *can* be represented. For example, *a/b* × *c/d*
is equal the reduced value of *ac/bd*, but either *ac* or *bd*
might overflow before the reduction. It is possible to avoid some of these
overflows by judicious use of the gcd in the implementation of the rational
arithmetic functions. Done properly,
`area.c`

can use much larger values of *N*:

%a.out 30 40 50 1600 170030: area=8990/13500 ~= 0.665926 40: area=21320/32000 ~= 0.66625 50: area=41650/62500 ~= 0.6664 1600: area=1365332800/2048000000 ~= 0.666666 1700: area=-853610036/-970333984 ~= 0.879707

Figure out how to avoid overflow in your implementation of the rational
functions and test it on
`area.c`

.
Explain your approach in your `readme`

file.

Turn in your code and your documentation with the command

/u/cs126/bin/submit 4 readme rat.c testrat.c

Do **not** turn in `rat.h`

or `area.c`

.

**References**

R. Sedgewick, Algorithms in C,
2nd ed., Addison-Wesley, 1990, pp. 8-9.

Copyright © 1996 David R. Hanson / drh@cs.princeton.edu

$Revision: 1.3 $ $Date: 1996/10/06 16:50:03 $