Consider the following two methods that compute the greatest common divisor of t
ID: 3883887 • Letter: C
Question
Consider the following two methods that compute the greatest common divisor of two integers. GCD(a, b) { n = min(a, b): for (int i = n: i > = 1: i--) if both a%1 and b%i are zero, return i: } Fastgcd (a, b) { if b equals 0, return a, else return Fastgcd(b, a %b): } Write a Java program that implements both of the above methods. Play with the program by giving very large numbers as inputs to both the numbers. (a) Pick two 9-digit primes and run both methods. Report the run time. (b) Pick two 10-digit primes and run both methods. Report the run time. (c) Show that the run time of FastGcd is O(n) when the inputs a and b are n-bit integers. Please do not submit your code. You can use System.currentTimeMillis() to calculate run time of your methods. You can look at https: //primes.utm.edu lists/small/millions/ for 9 digit primes. You can look at https: /primes.utni.edu/lists/small small.html for 10 digit primes.Explanation / Answer
import java.io.*;
class GFG {
public static int GCD(int a, int b) {
int n = Math.min(a, b);
for (int i = n; i >= 1; i--)
if (a % i == 0 && b % i == 0)
return i;
return 1;
}
public static int fastGCD(int a, int b) {
if (b == 0)
return a;
else
return fastGCD(b, a % b);
}
public static void main (String[] args) {
System.out.println("Checking run time for 9 digit prime numbers !");
long start = System.currentTimeMillis();
System.out.println(GCD(100030001, 100050001));
long end = System.currentTimeMillis();
System.out.println("Run time for GCD :" + (end - start));
start = end;
System.out.println(fastGCD(100030001, 100050001));
end = System.currentTimeMillis();
System.out.println("Run time for fastGCD :" + (end - start));
System.out.println("Checking run time for 10 digit prime numbers !");
start = end;
System.out.println(GCD(1000000007, 1000000787));
end = System.currentTimeMillis();
System.out.println("Run time for GCD :" + (end - start));
start = end;
System.out.println(fastGCD(1000000007, 1000000787));
end = System.currentTimeMillis();
System.out.println("Run time for fastGCD :" + (end - start));
}
}
Output :