Fund. CS II (CS152 2006S)

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.



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.

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.



Wednesday, 22 February 2006 [Samuel A. Rebelsky]


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

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

Samuel A. Rebelsky,