COS 126: Fall 1996
Rational Arithmetic		 Due: Wed. 10/9, 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 x2/(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 2x/3x 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 x2/(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 x2/(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 1700
30:     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 x2 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 1700
30:     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 $