Java Training Course/JT05

Greatest Common Divisor

Motivation

The goal of the next few sessions is the development of a real, useful Java class that is missing from the JDK.

This class will be named Rational. It will represent a fractional number consisting of:

• an integer numerator displayed above a line (or before a slash), and
• a non-zero integer denominator, displayed below that line (or after the slash),
• methods for the addition, subtraction, multiplication and division of 2 such Rationals,
• some additional, helper methods which are used internally in the class.

If you are not familiar with such rational numbers, you may read the Wikipedia article on fractions. A citation from there:

Fractional numbers can also be written without using explicit numerators or denominators, by using decimals, percent signs, or negative exponents (as in 0.01, 1%, and 10−2 respectively, all of which are equivalent to 1/100). An integer such as the number 7 can be thought of as having an implicit denominator of one: 7 equals 7/1.

We make a little distinction between fractions (in general; sometimes imprecise 0.33333...) and rationals (with the representation by a numerator and a denominator; 1/3 is always exact).

• Subtask 1: Explain how the 4 arithmetic operations for fractions were done in school.

Least Common Multiple (LCM)

Multiplication and division of rationals is very simple. But for addition and subtraction, the denominators must first be aligned to their so-called least common multiple (LCM).

• Subtask 2: Explain how you would compute the LCM.

Prime Number Factorization

The LCM may very easily be determined from the prime number factorization of the 2 denominators, but such a factorization is rather complicated and inefficient for big numbers. There is a simple formula which relates the LCM to the greatest common divisor (GCD):

lcm(a,b) = abs(a*b) / gcd(a,b)

Euclid's Algorithm for the GCD

For the computation of the GCD there was a very simple, famous, fast and important algorithm invented 2300 years ago by the greek mathematician Euclid.

• Main task:
  • Read about the [Euclidean algorithm.
  • Try to develop the program loop which exchanges the divisor and the rest.
  • Google several different implementations in Java, and compare them.
  • Be careful to obey the conventions for zero and negative numbers.
  • Incorporate your solution into a variation of class DupInt in a file GreatestCommonDivisor.java
  • Compile and run that class as follows:

java GreatestCommonDivisor 0 0
java GreatestCommonDivisor 0 1
java GreatestCommonDivisor 1 0
java GreatestCommonDivisor 1 1
java GreatestCommonDivisor 4 4 
java GreatestCommonDivisor 12 8
java GreatestCommonDivisor 3 5
java GreatestCommonDivisor 81 24
java GreatestCommonDivisor 4096 256

< Previous: JT04 Integer Arithmetic
> Next: JT06 Skeleton of Class Rational