# Java Training Course/JT05

## Control Structures: The 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 `Rational`s,
• 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.

• 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 Preliminary Class Ratio