In this problem we implement a small arithemetic package for rational numbers.

Section 3.3 of the text gives functions which implement a representation of rational numbers and operations for addition, subtraction, multiplication and division as well as relational functions, printing functions etc. Some problems remain unresolved. After performing several operations the numerator and denominator of a resulting rational number may have common factors. As additional operations are performed, the numerators and denominators may grow without bound. Another problem is that the representation of a rational number as a two element list is not as efficient as it could be. Perhaps a better representation would be a dotted pair.

Implement a greatest common divisor function:

(define gcd

(lambda (x y)

...))

which returns the largest positive integer which divides both x and y.

To implement gcd , you might use the fact that the greatest common divisor of x and y also divides the remainder of x divided by y . This means that for (define r (remainder x y)), (gcd x y) is equal to (gcd y r) . But r is always less than y and may, in fact, be zero. If r is zero then the greatest common divisor of x and y is y. If r is not zero, then this process may be repeated producing a new remainder which is zero or divisible by the greatest common divisor. Eventually a remainder of zero will be attained and the greatest common divisor is determined as the previous divisor. For example:

(gcd 206 40)=(gcd 40 6)=(gcd 6 4)=(gcd 4 2)=(gcd 2 0)=2

This algorithm is known as Euclid's algorithm.

Make an efficient implementation of the rational arithmetic package given in Section 3.3 of the text which uses a unique representation (no common factors in the numerator and denominator, denominator>0) for each rational number of:

(numerator . denominator).