Greates Commong Dividend - euklidischer Algorithmus, modulos not positive

[Lukases2]

Hallo wieder mal,

ich habe eine Methode geschrieben, die den größten gemeinsamen Teiler (= ggT = gcd = greates common dividend) mit Hilfe des euklidischen Algorithmus berechnet:

public BigInteger gcdEuclid(BigInteger n, BigInteger m){
		/* Beginne Initialisierung */
		BigInteger g = BigInteger.ZERO; // g = Lösung
		int zw = n.compareTo(m); // Vergleichsspeicher
		BigInteger a = BigInteger.ZERO; // erster Zwischenspeicher
		BigInteger b = BigInteger.ZERO; // zweiter Zwischenspeiche
		/* Beende Initialisierung */
		
		while(zw != 0){ 
				a = m;
				b = n.mod(m);
				n = a;
				m = b;
				zw = n.compareTo(m);
				g = n;
		}
		return g;
	}

Nach dem dritten Durchlauf der Schleife bekomme ich die "java.lang.ArithmeticException: BigInteger: modulus not positive". Ich komme nicht drauf, wie ich das beheben kann.

 

[Diabolus]

Ich hätte so eine Methode so geschrieben:

public int gcdEuclid(int n, int m){
	int h = 0;
	while(m != 0) {
		h = n%m;
		n = m;
		m = h;
	}
	return n;
}

mfg Diabolus

 

[Diabolus]

Natürlich würde es auch mit BigInteger gehen:

public BigInteger gcdEuclid(BigInteger n, BigInteger m) {
	BigInteger g = BigInteger.ZERO;
 
	while(!m.equals(BigInteger.ZERO)) { 
		g = n.mod(m);
		n = m;
		m = g;
	}
	return n;
}

mfg Diabolus

 

[Lukases2]

Ist das denn auch der euklidische Algorithmus? Der mir vorgegebene Pseudocode enthält nämlich diese a's und b's, die ich eben auch eingebaut habe.

 

[Diabolus]

Hallo Lukases2,

Ich kenne ja nicht deinen dir vorliegenden Pseudocode aber laut Wikipedia(Euklidischer Algorithmus – Wikipedia) lautet der iterative Algorithmus in Pseudocode wie folgend:

EUCLID(a,b)
1  solange b ≠ 0
2      h <- a mod b
3      a <- b
4      b <- h
5  return a

und hier der Javacode für diesen Pseudocode (als Kommentare hab ich das Pseudocode Pendant geschrieben):

public BigInteger gcdEuclid(BigInteger a, BigInteger b) {
    BigInteger h = BigInteger.ZERO;//initialisierung der variable h
 
    while(!b.equals(BigInteger.ZERO)) {  //solange b != 0
        h = a.mod(b);  //h <- a mod b
        a = b;  //a <- b
        b = h;  //b <- h
    }
    return a;  //return a
}

Wie du siehst ist das genau der Code den ich vorhin schon gepostet habe nur mit anderen Variablennamen!

mfg Diabolus

 

[Lukases2]

Ok ich erkenn's jetzt
Danke!