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.

Purposes: To help you further explore writing your own methods. To improve the class.

Contents:

• Background
• The Assignment
• Computing Greatest Common Divisors
• Submitting Your Work

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.

Submitting Your Work

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.