Implement a code to compute the gcd of a and b based on the Euclidean algorithm.
ID: 3545132 • Letter: I
Question
Implement a code to compute the gcd of a and b based on the Euclidean algorithm.
Also compute the coef?cients s and t where sa+tb = gcd(a;b) using the extended
Euclidean algorithm presented in class (Section 4.3). Use your implementation for
the following test cases:
1. a = 4001, b = 27
2. a = 3175, b = 192
3. a = 10;125, b = 9;037
4. a = 212;056, b = 105;772
How many iterations does the Euclidean algorithm take to compute the gcd of a
and b in each of the above test cases?
Use either Python, Java or Matlab. Submit your codes via the ICON dropbox, and
your answers by hardcopy in class on the due date.
Explanation / Answer
//part1
import java.util.Scanner;
public class Euclid {
// recursive implementation
public static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int p = sc.nextInt();
int q = sc.nextInt();
int d = gcd(p, q);
System.out.println("gcd(" + p + ", " + q + ") = " + d);
sc.close();
}
}
//Part2
import java.util.Scanner;
public class ExtendedEuclid {
// return array [d, a, b] such that d = gcd(p, q), ap + bq = d
static int[] gcd(int p, int q) {
if (q == 0)
return new int[] { p, 1, 0 };
int[] vals = gcd(q, p % q);
int d = vals[0];
int a = vals[2];
int b = vals[1] - (p / q) * vals[2];
return new int[] { d, a, b };
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int p = sc.nextInt();
int q = sc.nextInt();
int vals[] = gcd(p, q);
System.out.println("gcd(" + p + ", " + q + ") = " + vals[0]);
System.out.println(vals[1] + "(" + p + ") + " + vals[2] + "(" + q + ") = " + vals[0]);
sc.close();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.