# Java Training Course/JT05

## Contents

## 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.

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