Java Training Course/JT05: Difference between revisions

From tehowiki
Jump to navigation Jump to search
imported>Gfis
No edit summary
imported>Gfis
JT06 is Ratio
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
==Greatest Common Divisor==
==Control Structures: The Greatest Common Divisor==
===Motivation===
===Motivation===
The goal of the next few sessions is the development of a real, useful Java class that is missing from the JDK.  
The goal of the next few sessions is the development of a real, useful Java class that is missing from the JDK.  
Line 19: Line 19:
===Prime Number Factorization===
===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):
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)
:lcm(a,b) = abs(a*b) / gcd(a,b)
===Euclid's Algorithm for the GCD===
===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.
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:  
* Main task:  
** Read about the [[https://en.wikipedia.org/wiki/Euclidean_algorithm Euclidean algorithm].
** Read about the [https://en.wikipedia.org/wiki/Euclidean_algorithm Euclidean algorithm].
** Try to develop the program loop which exchanges the divisor and the rest.
** Try to develop the program loop which exchanges the divisor and the rest.
** Google several different implementations in Java, and compare them.
** Google several different implementations in Java, and compare them.
Line 39: Line 39:
  java GreatestCommonDivisor 4096 256
  java GreatestCommonDivisor 4096 256
[[Java Training Course/JT04|&lt; Previous: JT04]] Integer Arithmetic<br />
[[Java Training Course/JT04|&lt; Previous: JT04]] Integer Arithmetic<br />
[[Java Training Course/JT06|&gt; Next: JT06]] Skeleton of Class ''Rational''
[[Java Training Course/JT06|&gt; Next: JT06]] Preliminary Class ''Ratio''

Latest revision as of 19:25, 26 September 2017

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