# Homework 10: Simplifying Fractions

Assigned: Wednesday, February 22, 2006
Due: 8:00 a.m., Friday, February 24, 2006

Summary: In this assignment, you will improve the `Fraction` class by adding support for simplifying fractions.

Contents:

## Background

In the lab on writing your own classes, you extended a `Fraction` class that I had begun to write.

As you've noted, one potential problem with the class is that it rarely expresses fractions in simplest form. It is, however, relatively easy to simplify fractions: You just divide the numerator and denominator by their greatest common divisor.

## The Assignment

a. Write a `simplify` object method that simplifies the current fraction. As suggested above, you simplify a fraction by dividing the numerator and denominator by their greatest common divisor.

b. Verify that your method works.

c. Update the constructors of `Fraction` so that they simplify each fraction as soon as it is created.

## Computing Greatest Common Divisors

Of course, to do this assignment, you will need to know how to compute the greatest common divisor of any two integers (or at least of any two positive integers). That computation is fairly easy to express recursively.

• The greatest common divisor of a negative number, n, and another number, m is the greates common divisor of the absolute value of n and m.
• The greatest common divisor of a positive number, n, and 0 is n.
• If n is greater than or equal to m, and both m and n are positive, the greatest common divisor of m and n is the same as the greatest common divisor of m and the remainder you get when dividing n by m.

In Scheme, we might phrase this as

```(define gcd
(letrec ((gcd-kernel
(lambda (m n)
(cond ((= 0 n) m)
((= 0 m) n)
((> m n) (gcd-kernel n (remainder m n)))
((> n m) (gcd-kernel m (remainder n m)))
(else #f))))) ; Should never happen
(lambda (m n)
(gcd-kernel (abs m) (abs n)))))
```

A little analysis tells us that when n is less than m, the remainder is still n. Hence, we can swap the values by using the same process. The method then simplifies to

```(define gcd
(letrec ((gcd-kernel
(lambda (m n)
(if (= 0 n) m
(gcd-kernel n (remainder m n))))))
(lambda (m n)
(gcd-kernel (abs m) (abs n)))))
```

You will, of course, have to rewrite this method in Java.

When you are satisfied with your work, send me the code of `simplify` and `gcd`. You need not send your enclosing class or test methods.

## History

Wednesday, 22 February 2006 [Samuel A. Rebelsky]

• Created.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 9 08:31:10 2006.
The source to the document was last modified on Wed Feb 22 11:24:37 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Homework/hw.10.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu