Implementing Euclid's Algorithm

Implement the Pseudo-codes of Euclid’s Algorithm

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

 

Implementing Euclid's Algorithm
Implementing Euclid’s Algorithm

You may also like to read:

  1. C Program to Find GCD

  2. C Program to Print Fibonacci Numbers

  3. Kattis Problem: Batter Up

  4. Kattis Problem: Faktor

  5. Structures and Unions in C Programming