HTW Berlin
Fachbereich 4
Internationaler Bachelor Studiengang
Internationale Medieninformatik (Bachelor)
Info 2: Informatik II
Summer Term 2023
|
|
|
HTW Berlin |
Algorithmus |
|
Euclid of Alexandria (Greek : Εὐκλείδης, Eukleides) (* circa 365; † 275 BC) was a Greek mathematician, now known as "the father of geometry". His most famous work is Elements, widely considered to be history's most successful textbook. Within it, the properties of geometrical objects and integers are deduced from a small set of axioms, thereby anticipating (and partly inspiring) the axiomatic method of modern mathematics.1 Elements: Book VII, Proposition 2: „To find the greatest common measure of two given numbers not relatively prime. Let AB and CD be the two given numbers not relatively prime. It is required to find the greatest common measure of AB and CD. If now CD measures AB, since it also measures itself, then CD is a common measure of CD and AB. And it is manifest that it is also the greatest, for no greater number than CD measures CD. But, if CD does not measure AB, then, when the less of the numbers AB and CD being continually subtracted from the greater, some number is left which measures the one before it. For a unit is not left, otherwise AB and CD would be relatively prime, which is contrary to the hypothesis. Therefore some number is left which measures the one before it. Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE. Since then, CF measures AE, and AE measures DF, therefore CF also measures DF. But it measures itself, therefore it also measures the whole CD. But CD measures BE, therefore CF also measures BE. And it also measures EA, therefore it measures the whole BA. But it also measures CD, therefore CF measures AB and CD. Therefore CF is a common measure of AB and CD. I say next that it is also the greatest. If CF is not the greatest common measure of AB and CD, then some number G, which is greater than CF, measures the numbers AB and CD. Now, since G measures CD, and CD measures BE, therefore G also measures BE. But it also measures the whole BA, therefore it measures the remainder AE. But AE measures DF, therefore G also measures DF. And it measures the whole DC, therefore it also measures the remainder CF, that is, the greater measures the less, which is impossible. Therefore no number which is greater than CF measures the numbers AB and CD. Therefore CF is the greatest common measure of AB and CD. CorollaryFrom this it is manifest that, if a number measures two numbers, then it also measures their greatest common measure. " 3["Number AB" means the distance between point A and point B. ] |
The following Java method uses this Euclidian algorithm:
public int euclid1 (int n1, int n2){
int m1 = n1;
int m2 = n2;
while (m1 != m2) {
if (m1 > m2) {
m1 = m1 - m2;
} else {
m2 = m2 - m1;
}
}
return m1;
}
The following method also computes the Euclidian algorithm, using something called recursion, which we have not yet had:
public int euclid2 (int n1, int n2){
if (n1 > n2) {
return euclid2 (n1-n2, n2);
}
else
if (n2 > n1) {
return euclid2 (n1, n2-n1);
}
else { // n1==n2
return n1;
}
}
These are three different representations with Euclid's algorithm. The translation is quite abstract, that is, there are lots of details that are not specified. Both Java methods are quite concrete. The algorithm is ths abstract idea, which is common to all three representation
Here's another one, let's call this one gcd:
public int gcd (int n1, int n2){
for (int i = max (n1, n2); i > 0; i--){
if ((n1%i == 0) && (n2%i == 0)){
return i;
}
}
return -1;
}
This method also calculates the greatest common divisor of two integers > 0. But nowhere do we have the larger number being subtracted from the smaller one, do we? Is this a Euclidian algorithm or is it another algorithm for calculating the gcd? What about this one:
public int strange (int n1, int n2){
int m1 = n1;
int m2 = n2;
while ((m1 != 0) && (m2 != 0)) {
if (m1 > m2) {
m1 = m1%m2;
} else {
m2 = m2%m1;
}
}
return m1 + m2;
}
This is rather similar to euclid1, but again, we don't have the smaller being taken away from the larger one, so is this the Euclidian algorithm? How about this one:
public int stranger (int n1, int n2){
int m1 = n1;
int m2 = n2;
while (m1 != m2) {
if (m1 > m2) {
while (m1 > m2) { m1 = m1 - m2;};
} else {
while (m2 > m1) { m2 = m2 - m1;};
}
}
return m1;
}
Is this method using the Euclidian algorithm or not?
