CS 4: Lecture 15
Monday, March 13, 2006
The Fraction Class (continued from Lecture 14)
------------------
Recall that, last lecture, we were writing a class for rational numbers.
public class Fraction {
private long numerator;
private long denominator;
Besides the two constructors we wrote then, it's also useful to have a
constructor that copies a Fraction.
public Fraction(Fraction original) {
this(original.numerator, original.denominator);
}
Now, we can use Fractions to divide rationals exactly. If you divide a
fraction a/b by another fraction c/d, the result is ad/(bc).
public void divide(Fraction f) {
numerator = numerator * f.denominator;
denominator = denominator * f.numerator;
reduce();
}
This method operates on two Fractions: the Fraction "f", and another fraction
called "this".
The "this" Keyword
------------------
The method invocation frac1.divide(frac2) implicitly passes the object "frac1"
as a parameter called "this". So we could rewrite the divide method as follows
without changing its meaning.
public void divide(Fraction f) {
this.numerator = this.numerator * f.denominator;
this.denominator = this.denominator * f.numerator;
reduce();
}
In this case, "this" is optional.
However, sometimes you need "this". For example, sometimes you want to divide
two fractions without changing one of them. Let's write a method called
"quotient" that constructs a new Fraction instead of modifying an existing one.
public Fraction quotient(Fraction f) {
Fraction result = new Fraction(this);
result.divide(f);
return result;
}
The first line creates a new Fraction that is a copy of the Fraction the method
was called on. For example, suppose we invoke this method by writing
frac3 = frac1.quotient(frac2);
Just before the "quotient" method finishes, the references and objects look
like this.
------------- ------------- -------------
| numerator | | numerator | | numerator |
--- | ----- | --- | ----- | | ----- |
frac1 |.+-->| | 3 | | frac2 |.+-->| | 2 | | | | 9 | |
--- | ----- | --- | ----- | | ----- |
| | | | | |
--- | ----- | --- | ----- | --- | ----- |
this |.+-->| | 4 | | f |.+-->| | 3 | | result |.+-->| | 8 | |
--- | ----- | --- | ----- | --- | ----- |
|denominator| |denominator| |denominator|
------------- ------------- -------------
These variables are in two different scopes.
- The scope of "frac1" and "frac2" is the calling method, where the line
"frac3 = frac1.quotient(frac2);" appears.
- The scope of "this", "f", and "result" is the method Fraction.quotient.
The KEY POINT is that when we call "frac1.quotient(frac2)", frac1 is passed to
the quotient method as a parameter called _this_. It doesn't appear in the
parameter list, but it's still being passed.
When you write "numerator" inside a method in the Fraction class, Java
interprets it as "this.numerator".
There are two very important things you must memorize about "this".
(1) You cannot change the value of "this"!
A statement like "this = frac2" will trigger a compile-time error.
(2) In a _static_ method, THERE IS NO "this"!
Using "divide" and "quotient"
-----------------------------
Observe that "divide" and "quotient" both do rational division, but they're
used slightly differently.
frac3 = frac1.quotient(frac2); // frac3 = frac1 / frac2;
frac1.divide(frac2); // frac1 = frac1 / frac2;
Euclid's GCD algorithm
----------------------
During the last lecture, I mentioned a "reduce()" method that reduces a
fraction like 6/9 to its simplest form. How can we do that? Observe that
6 and 9 are both divisible by 3, so we have
6 6/3 2
- = --- = -,
9 9/3 3
which is the simplest form of the fraction.
More generally, to reduce a fraction n/d to its simplest form, we find the
_greatest_common_divisor_ (GCD) of n and d, and divide both of them by the GCD.
How do we compute a GCD?
Euclid of Alexandria described an algorithm for computing GCDs about 2,300
years ago, in Book VII of the _Elements_, the most famous math textbook ever.
It's one of the oldest known algorithms. I don't know of any earlier formal
algorithm except the algorithms for doing simple arithmetic by hand (like you
learned in grade school). Before we see Euclid's algorithm, let's look at the
mathematics behind it.
Let GCD(a, b) be the GCD of a and b. Find GCD(a, b) is easy if one of the
numbers is zero.
GCD(a, 0) = a. (Zero is divisible by everything.)
What if neither a nor b is zero? Let
q = floor(a / b), which means a / b rounded down to the nearest integer, and
r = remainder(a / b).
By the definition of "remainder,"
a = qb + r.
This formula allows us to "simplify" GCD(a, b). Let's prove it.
Theorem: If a and b are divisible by some integer g, then so is r.
Proof: Because a and b are divisible by g, there are integers x and y such
that a = xg and b = yg.
So, r = a - qb = xg - qyg = (x - qy) g.
Since q, x, and y are integers, so is (x - qy), so r is divisible by g. QED
Theorem: GCD(a, b) = GCD(b, r).
Proof: Because a and b are divisible by GCD(a, b), so is r (see proof above).
Because b and r are divisible by GCD(b, r), so is qb + r = a.
Therefore, a, b, and r are all divisible by both GCD(a, b) and GCD(b, r).
If GCD(a, b) > GCD(b, r), then GCD(b, r) isn't really the _greatest_ common
divisor of b and r, because GCD(a, b) is greater. --> GCD(a, b) <= GCD(b, r).
If GCD(a, b) < GCD(b, r), then GCD(a, b) isn't really the _greatest_ common
divisor of a and b, because GCD(b, r) is greater. --> GCD(a, b) >= GCD(b, r).
Therefore, GCD(a, b) = GCD(b, r). QED
The algorithm
-------------
The idea of the algorithm is to replace "GCD(a, b)" with "GCD(b, r)", and do it
over and over. The key is that r is always smaller than b. Because we keep
replacing b with a smaller number, eventually we will whittle it down to zero,
and we can use "GCD(a, 0) = a" to finish.
Let's compute GCD(21, 78) by hand.
Dividing 21 by 78 gives 0 with remainder 21. So GCD(21, 78) = GCD(78, 21).
Dividing 78 by 21 gives 3 with remainder 15. So GCD(78, 21) = GCD(21, 15).
Continuing this way, we have
GCD(21, 78) = GCD(78, 21)
= GCD(21, 15)
= GCD(15, 6)
= GCD(6, 3)
= GCD(3, 0)
= 3.
Observe that the second operand of GCD gets smaller on every iteration. That
gives us a guarantee that the algorithm won't run forever.
Now let's write a method that computes a GCD.
static private long gcd(long a, long b) {
while (b > 0) {
long remainder = a % b;
a = b;
b = remainder;
}
return a;
}
The method is static because it doesn't operate on a Fraction; it just computes
the GCD of two parameters. Note that the code doesn't even need to compute
a / b; just a % b. It's short and very fast.
Now we can use the gcd method to reduce Fractions and make sure the denominator
is positive. (This method is NOT static.)
private void reduce() {
long divisor = gcd(numerator, denominator);
numerator = numerator / divisor;
denominator = denominator / divisor;
if (denominator < 0) {
numerator = -numerator;
denominator = -denominator;
}
}
A random closing thought: Euclid's algorithm requires the most iterations when
you run it on two large successive Fibonacci numbers.