int exeuclid(int a, int m)
{
int A3 = m;
int A2 = 0, A1 = 1;
if (m == 1)
return 0;
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = A2;
// Update A1 and A2
A2 = A1 - q * A2;
A1 = t;
}
// Make A1 positive
if (A1 < 0)
A1 += A3;
return A1;
}
Let us look into how to implement Euclid’s algorithm and Euclid’s Extended Algorithms using Java Programming Language.
Euclid’s Algorithm Pseudocode
int euclid(int a, int b){
if(b==0)
return a;
else
return euclid(b, a%b);
}
Euclid’s Extended Algorithm Pseudocode
int exeuclid(int a, int m)
{
int A3 = m;
int A2 = 0, A1 = 1;
if (m == 1)
return 0;
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = A2;
// Update A1 and A2
A2 = A1 - q * A2;
A1 = t;
}
// Make A1 positive
if (A1 < 0)
A1 += A3;
return A1;
}
Question
Implement the pseudo-codes of Euclid’s algorithm with recursive function and extended Euclid’s algorithm in any programming language you are comfortable with. Your program should take two integers A and B as inputs and give either as GCD (A, B) = d or B-1 = y.
1) Determine the
a) gcd(72345, 43215)
b) gcd(2740, 1760)
2) Find the multiplicative inverse of
a. 550 mod 1769
b. 7465 mod 2464
c. 42828 mod 6407
Sample Program
import java.util.Scanner;
class Lab3{
//euclids algorithm
int euclid(int a, int b){
if(b==0)
return a;
else
return euclid(b, a%b);
}
//euclids extended algorithm
int exeuclid(int a, int m)
{
int A3 = m;
int A2 = 0, A1 = 1;
if (m == 1)
return 0;
while (a > 1)
{
// q is quotient
int q = a / m;
int t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = A2;
// Update A1 and A2
A2 = A1 - q * A2;
A1 = t;
}
// Make A1 positive
if (A1 < 0)
A1 += A3;
return A1;
}
public static void main(String[] args) {
Lab3 ob = new Lab3();
int x, y, choice;
Scanner input = new Scanner(System.in);
System.out.println("Enter Choice \n Enter 1 for gcd and 2 for extended ed");
choice=input.nextInt();
switch(choice)
{
case 1:
int output;
System.out.println("Enter the first number");
x = input.nextInt();
System.out.println("Enter the second number");
y = input.nextInt();
output = ob.euclid(x, y);
System.out.println("GCD is:"+output);
break;
case 2:
System.out.println("To Find Inverse");
int m, b;
System.out.println("Enter m");
m=input.nextInt();
System.out.println("Enter b");
b = input.nextInt();
System.out.println("Inverse is equal to: "+ob.exeuclid(m, b));
break;
default:
System.out.println("Wrong Choice");
}
}
}
Sample Output
You may also like to read: