Euklidischer Algorithmus in Java

Einleitung

Ein bekannter Algorithmus zum Berechnen des größten gemeinsamen Teilers (kurz: ggT), ist der euklidische Algorithmus und in diesem Artikel soll genau dieser Algorithmus in Java nachkonstruiert werden.

Main.java

Auch dieses Mal wird wieder das String-Array args aus der main-Funktion benutzt um die Benutzeingabe abzufragen. Da dieses Mal keine zusätzlichen Bibliotheken benötigt werden, beginne ich mit gleich mit der Verarbeitung der Benutzeingabe:

if (args.length == 2) {
    char[] first_number = args[0].toCharArray();
    char[] second_number = args[1].toCharArray();
    if (check_number(first_number) == true) {
        if (check_number(second_number) == true) {}
    }
}

Auch in diesem Code habe ich das String-Array in ein Char-Array umgeformt, damit die einzelnen Character in der check_number-Funktion gelesen werden können:

if (((int)c < 48 || (int)c > 57) && c != '+' && c != '-') {
    valid_number = false;
    break;
}

Zuerst soll in der Funktion überprüft werden, ob der einzelne Character eine Zahl zwischen 0 und 9, ein Plus oder ein Minus ist. Sollte das nicht der Fall sein, ist der Character und somit die gesamte Eingabe ungültig.

if (counter > 0 && (c == '+' || c == '-')) {
    valid_number = false;
    break;
}

Nun wird überprüft, ob ein Plus oder ein Minus nicht zu Beginn der Zahl steht. Trifft dieser Fall ein, ist die Eingabe ebenfalls ungültig. Die nächste und auch letzte if-Abfrage verändert das Vorzeichen vom Minus zum Plus, da beim Herausfinden des ggT das Vorzeichen hier vernachlässigt wird.

if (c == '-') {
    number[counter] = '+';
}

Nachdem nun sichergestellt wurde, dass die Benutzereingabe korrekt ist, werden die char-Arrays in integer umgewandelt, da später noch ein paar Rechnungen durchgeführt werden müssen. Erledigt wird dies wieder in einer separaten Funktion 'convert_char_number_to_integer':

public static int convert_char_number_to_integer(char[] number) {
    return Integer.parseInt(new String(number));
}

Man hätte es wieder unnötig kompliziert gestalten können - dazu kommen wir gleich - doch wie man sieht, habe ich eine bereits existierende Funktion benutzt. Doch zum Lernen wollte ich natürlich das gleiche Resultat selbst konstruieren:

public static int comp_char_number_to_integer(char[] number) {
    int num = 0;
    for (char n : number) {
        num = (num * 10 + (n - 48));
    }
    return num;
}

Innerhalb der for-Schleife wird jeder character zuerst in eine Ganzzahl umgewandelt (n - 48) um danach mit num * 10 verrechnet zu werden. Dabei ist der erste Durchlauf immer num * 10 gleich Null. Da wir nun die beiden Ganzzahlen besitzen, können wir mit dem eigentlichen euklidischen Algorithmus beginnen:

public static int recursive_euklidic_algorithm(int a, int b) {
    if (a == 1 || b == 1 || a == b) {
        if (a == 1) {
            return a;
        }
        return b;
    } else {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
        return recursive_euklidic_algorithm(a, b);
    }
}

Das ist eine rekursive Funktion, was für sehr große Zahlen ein sehr großes Problem werden könnte. Deshalb benötigen wir auch noch eine iterative-Funktion:

public static int iterative_euklidic_algorithm(int a, int b) {
    while (a != b && a != 1 && b != 1) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    if (a == 1) {
        return a;
    }
    return b;
}

Das zuvor erwähnte große Problem bei der rekursiven Funktion lässt das Programm zum Absturz bringen, da die Rekursionstiefe überschritten wird. Jedes mal, wenn die Funktion erneut aufgerufen wird, wird neuer Speicher vom Stack benötigt, wessen Größe natürlich begrenzt ist. Es kann sich jedoch auch um einen Ganzzahlüberlauf handeln, da Datentypen wie int eine begrenzte Größe repräsentieren können. Wie groß ein Integer sein darf ist vom Compiler und von der Systemarchitektur abhängig.

Man könnte den Code verbessern und die Anzahl an Rechenschritte signifikant verringern, wenn man die Berechnung mit modulo berechnet. Für die iterative Funktion würde das dementsprechend so aussehen:

while (b != 0) {
    int temp = b;
    b = a % b;
    a = temp;
}
return a;

Der gesamte Code kann wie immer bei meinen GitHub-Account zu finden: /Learning-JAVA/euclideanalgorithm