Java Training Course/JT05

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)

Greatest Common Divisor (GCD)

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

• Main task:
  • Read about Euclid's algorithm.
  • Try to develop the program loop which exchanges the divisor and the rest.
  • Google several different implementation in Java, and compare them.
  • Be careful to obey the conventions for zero and negative numbers.
  • Incorporate your solution into a variation of DupInt called GreatestCommonDivisor.java
  • Compile and run it 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