# gestellter Code fehlerhaft?



## Lukases2 (28. Apr 2015)

Ich habe als Hausaufgabe folgenden Code bekommen:


```
import java.math.BigInteger;
import java.util.Random;

public class Gcd {
	public static BigInteger gcdNaive(BigInteger a, BigInteger b) {
		// bitte implementieren Sie diese Methode
		return BigInteger.ZERO;
	}
	public static BigInteger gcdEuclid(BigInteger a, BigInteger b) {
		// bitte implementieren Sie diese Methode
		return BigInteger.ZERO;
	}

	public static boolean testNaive(int sample_size, int num_bits, Random random) {
		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger gcd = gcdNaive(a, b);

			if(!gcd.equals(a.gcd(b))) {
				System.out.println("Naive algorithm: Wrong solution!");
				System.out.println("    for gcd(" + a + ", " + b + "):"
						+ " Expected " + a.gcd(b) + " but got " + gcd);
				return false;
			}
		}

		return true;
	}
	
	public static boolean testEuclid(int sample_size, int num_bits, Random random) {
		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger gcd = gcdEuclid(a, b);

			if(!gcd.equals(a.gcd(b))) {
				System.out.println("Euclidean algorithm: Wrong solution!");
				System.out.println("    for gcd(" + a + ", " + b + "):"
						+ " Expected " + a.gcd(b) + " but got " + gcd);
				return false;
			}
		}

		return true;
	}

	public static long benchmarkNaive(int sample_size, int num_bits, Random random) {
		long time_sum = 0;

		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);

			long start = System.nanoTime();
			BigInteger gcd = gcdNaive(a, b);
			time_sum += System.nanoTime() - start;

			if(!gcd.equals(a.gcd(b)))
				System.out.println("Naive algorithm: Wrong solution!");
		}

		return time_sum / sample_size;
	}
	
	public static long benchmarkEuclid(int sample_size, int num_bits, Random random) {
		long time_sum = 0;

		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);

			long start = System.nanoTime();
			BigInteger gcd = gcdEuclid(a, b);
			time_sum += System.nanoTime() - start;

			if(!gcd.equals(a.gcd(b)))
				System.out.println("Euclidean algorithm: Wrong solution!");
		}

		return time_sum / sample_size;
	}

	public static void main(String[] args) {
		Random random = new Random();
		
		boolean ok = true;
		if(!testNaive(100, 16, random)) {
			ok = false;
		}else{
			System.out.println("Naive algorithm seems to be correct!");
		}
		if(!testEuclid(100, 16, random)) {
			ok = false;
		}else{
			System.out.println("Euclidean algorithm seems to be correct!");
		}
		if(!ok)
			return;

		int sample_size = 10;
		
		System.out.println("Benchmark:");
		System.out.println(String.format("%12s %24s %24s",
				"#bits", "runtime (naive)", "runtime (Euclidean)"));
		
		int num_bits = 4;
		while(true) {
			long naive_time = benchmarkNaive(sample_size, num_bits, random);
			long euclid_time = benchmarkEuclid(sample_size, num_bits, random);

			System.out.println(String.format("%12s %24s %24s", num_bits,
				((naive_time / 1000000L) + "." + String.format("%06d", naive_time % 1000000L)),
				((euclid_time / 1000000L) + "." + String.format("%06d", euclid_time % 1000000L))));

			if(naive_time * sample_size > 5L * 1000000000L
					|| euclid_time * sample_size > 5L * 1000000000L)
				break;
			
			num_bits = num_bits << 1;
		}
		System.out.println("All timings are averages over " + sample_size
				+ " runs measured in ms");
	}
};
```

Er soll ein Programm darstellen, welches mit anzeigt, ob die von mir (noch nicht) implementierten Methoden, die den größten gemeinsamen Teiler (= greates commen dividend = gcd) auf euklidischer oder naive Art errechnen sollen, korrekt sind. 

Wenn ich das Programm starte, bekomme ich folgende Fehlermeldung:


> Exception in thread "main" java.lang.Error: Unresolved compilation problems:
> The method format(Locale, String, Object[]) in the type String is not applicable for the arguments (String, String, String, String)
> The method format(String, Object[]) in the type String is not applicable for the arguments (String, long)
> The method format(String, Object[]) in the type String is not applicable for the arguments (String, long)
> ...



Wenn ich die Methoden implementiere, bekomme ich natürlich immer noch die gleiche Fehlermeldung. Wir sollen nicht (wir _dürfen_ sogar nicht) am sonstigen Code basteln. Ist der Code fehlerhaft?


----------



## stg (28. Apr 2015)

Welche Java Version benutzt du? 
Welche IDE benutzt du?
Welchen Complience Level hast du dort eingestellt?


----------



## Lukases2 (29. Apr 2015)

Java Version: 1.8.0_40
IDE: Ich arbeite zurzeit an einem PC der Uni, keine Ahnung, welche IDE die da installiert haben. Wie finde ich das heraus? Eclipse ist auf jeden Fall diese KEPLER-Version. 
Compilence Level: Habe ich noch nie was von gehört. Wie finde ich das heraus?


----------



## stg (29. Apr 2015)

Eclipse Kepler IST die IDE 

Mach mal einen Rechtsklick auf dein Projekt.
Unter "Properties" -> "Java Compiler" findest du die Compliance Einstellungen.
Stell das einfach mal auf den höchstmöglichen Wert... (mindestens aber Java 1.5)


----------



## Lukases2 (29. Apr 2015)

Es war auf Java 1.4 eingestellt, das habe ich jetzt geändert und es funktioniert alles. 
Sehr gut, danke 

Hier nochmal der Code mit implementierten Methoden:


```
import java.math.BigInteger;
import java.util.Random;

public class Gcd {
public static BigInteger gcdNaive(BigInteger n, BigInteger m){
		
		/* Beginn der Initialisierung */
		BigInteger g = BigInteger.ZERO; // g = Lösung
		int zw = n.compareTo(m); // Vergleichsspeicher
		/* Ende der Initialisierung */
		
		while(zw != 0){
			if(zw == 1){
				n = n.subtract(m);
				zw = n.compareTo(m);
				g = n;
			}
			else if(zw == -1){
				m = m.subtract(n);
				zw = n.compareTo(m);
				g = n;
			}
		}
		return g;
	}
	
	public static BigInteger gcdEuclid(BigInteger a, BigInteger b) {
		BigInteger g = BigInteger.ZERO;
		 
		while(!b.equals(BigInteger.ZERO)) {
		g = a.mod(b);
		a = b;
		b = g;
		}
		return a;
	}

	public static boolean testNaive(int sample_size, int num_bits, Random random) {
		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger gcd = gcdNaive(a, b);

			if(!gcd.equals(a.gcd(b))) {
				System.out.println("Naive algorithm: Wrong solution!");
				System.out.println("    for gcd(" + a + ", " + b + "):"
						+ " Expected " + a.gcd(b) + " but got " + gcd);
				return false;
			}
		}

		return true;
	}
	
	public static boolean testEuclid(int sample_size, int num_bits, Random random) {
		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger gcd = gcdEuclid(a, b);

			if(!gcd.equals(a.gcd(b))) {
				System.out.println("Euclidean algorithm: Wrong solution!");
				System.out.println("    for gcd(" + a + ", " + b + "):"
						+ " Expected " + a.gcd(b) + " but got " + gcd);
				return false;
			}
		}

		return true;
	}

	public static long benchmarkNaive(int sample_size, int num_bits, Random random) {
		long time_sum = 0;

		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);

			long start = System.nanoTime();
			BigInteger gcd = gcdNaive(a, b);
			time_sum += System.nanoTime() - start;

			if(!gcd.equals(a.gcd(b)))
				System.out.println("Naive algorithm: Wrong solution!");
		}

		return time_sum / sample_size;
	}
	
	public static long benchmarkEuclid(int sample_size, int num_bits, Random random) {
		long time_sum = 0;

		for(int i = 0; i < sample_size; i++) {
			BigInteger a = new BigInteger(num_bits, random).add(BigInteger.ONE);
			BigInteger b = new BigInteger(num_bits, random).add(BigInteger.ONE);

			long start = System.nanoTime();
			BigInteger gcd = gcdEuclid(a, b);
			time_sum += System.nanoTime() - start;

			if(!gcd.equals(a.gcd(b)))
				System.out.println("Euclidean algorithm: Wrong solution!");
		}

		return time_sum / sample_size;
	}

	public static void main(String[] args) {
		Random random = new Random();
		
		boolean ok = true;
		if(!testNaive(100, 16, random)) {
			ok = false;
		}else{
			System.out.println("Naive algorithm seems to be correct!");
		}
		if(!testEuclid(100, 16, random)) {
			ok = false;
		}else{
			System.out.println("Euclidean algorithm seems to be correct!");
		}
		if(!ok)
			return;

		int sample_size = 10;
		
		System.out.println("Benchmark:");
		System.out.println(String.format("%12s %24s %24s",
				"#bits", "runtime (naive)", "runtime (Euclidean)"));
		
		int num_bits = 4;
		while(true) {
			long naive_time = benchmarkNaive(sample_size, num_bits, random);
			long euclid_time = benchmarkEuclid(sample_size, num_bits, random);

			System.out.println(String.format("%12s %24s %24s", num_bits,
				((naive_time / 1000000L) + "." + String.format("%06d", naive_time % 1000000L)),
				((euclid_time / 1000000L) + "." + String.format("%06d", euclid_time % 1000000L))));

			if(naive_time * sample_size > 5L * 1000000000L
					|| euclid_time * sample_size > 5L * 1000000000L)
				break;
			
			num_bits = num_bits << 1;
		}
		System.out.println("All timings are averages over " + sample_size
				+ " runs measured in ms");
	}
};
```


----------

