How to write Extended Euclidean Algorithm code wise in Java?

Question

I have a question which is actually requires a bit of understanding Euclidian Algorithm. Problem is simple. An int "First" and int "Second" numbers are given by the user via Scanner. Than we need to find greatest common divisor of them. Than the process goes like explained below:

Now Assume that the First number is: 42 and the Second is: 30 - they've given by the user. -

int x, y;

(x * First) + (y * Second) = gcd(First, Second); // x ? y ?

To Find GCD you may use: gcd(First, Second); Code is below:

public static int gcd(int a, int b)    
    {    
        if(a == 0 || b == 0) return a+b; // base case   
        return gcd(b,a%b);    
    }    

Sample Input: First: 24 Second: 48 and Output should be x: (-3) and y: 2
Sample Input: First: 42 Second: 30 and Output should be x: (-2) and y: 3
Sample Input: First: 35 Second: 05 and Output should be x: (0) and y: 1

 (x * First) + (y * Second) = gcd(First, Second); // How can we find x and y ? 

I would very appreciate it if you could show a solution code wise in java thanks for checking!

Answer 1

Here is the code that I came up with if anyone is still looking. It is in C# but I am sure it similar to java. Enjoy

    static void Main(string[] args)
    {
        List<long> U = new List<long>();
        List<long> V = new List<long>();
        List<long> W = new List<long>();

        long a, b, d, x, y;

        Console.Write("Enter value for a: ");
        string firstInput = Console.ReadLine();
        long.TryParse(firstInput, out a);

        Console.Write("Enter value for b: ");
        string secondInput = Console.ReadLine();
        long.TryParse(secondInput, out b);

        long temp;
        //Make sure that a > b
        if(a < b)
        {
            temp = a;
            a = b;
            b = temp;
        }
        //Initialise List U
        U.Add(a);
        U.Add(1);
        U.Add(0);

        //Initialise List V
        V.Add(b);
        V.Add(0);
        V.Add(1);

       while(V[0] > 0)
        {
            decimal difference = U[0] / V[0];
            var roundedDown = Math.Floor(difference);
            long rounded = Convert.ToInt64(roundedDown);

            for (int i = 0; i < 3; i++)
                W.Add(U[i] - rounded * V[i]);

            U.Clear();
            for (int i = 0; i < 3; i++)
                U.Add(V[i]);

            V.Clear();
            for (int i = 0; i < 3; i++)
                V.Add(W[i]);

            W.Clear();

        }

       d = U[0];
       x = U[1];
       y = U[2];
       Console.WriteLine("\nd = {0}, x = {1}, y = {2}", d, x, y);

        //Check Equation
        Console.WriteLine("\nEquation check: d = ax + by\n");
        Console.WriteLine("\t{0} = {1}({2}) + {3}({4})", d, a, x, b, y);
        Console.WriteLine("\t{0} = {1} + {2}", d, a*x, b*y);
        Console.WriteLine("\t{0} = {1}", d, (a * x) + (b * y));
        if (d == (a * x) + (b * y))
            Console.WriteLine("\t***Equation is satisfied!***");   
        else
            Console.WriteLine("\tEquation is NOT satisfied!");
    }
}

}

Answer 2

Thank's for helping me out ajb I solved it after digging your answer. So for the people who would like to see code wise:

public class Main    
{    
public static void main (String args[])   
{   
    @SuppressWarnings("resource")    
    System.out.println("How many times you would like to try ?")
    Scanner read = new Scanner(System.in);    
    int len = read.nextInt();    

    for(int w = 0; w < len; w++)    
    {
        System.out.print("Please give the numbers seperated by space: ")
        read.nextLine();
        long tmp = read.nextLong();
        long m = read.nextLong();
        long n;
        if (m < tmp) {      
            n = m;
            m = tmp;
        }
        else {
            n = tmp;
        }

        long[] l1 = {m, 1, 0};
        long[] l2 = {n, 0, 1};
        long[] l3 = new long[3]; 

        while (l1[0]-l2[0]*(l1[0]/l2[0]) > 0) {
            for (int j=0;j<3;j++) l3[j] = l2[j]; 
            long q = l1[0]/l2[0];        
            for (int i = 0; i < 3; i++) {
            l2[i] = (l1[i]-l2[i]*q);
            }

            for (int k=0;k<3;k++) l1[k] = l3[k];
        }

        System.out.printf("%d %d %d",l2[1],l2[2],l2[0]); // first two Bezouts identity Last One gcd
    }
}
}    

Answer 3

The Extended Euclidean Algorithm is described in this Wikipedia article. The basic algorithm is stated like this (it looks better in the Wikipedia article):

More precisely, the standard Euclidean algorithm with a and b as input, consists of computing a sequence q₁,..., q_k of quotients and a sequence r₀,..., r_k+1 of remainders such that

r₀=a
r₁=b
...
r_i+1=r_i-1-q_i r_i and 0 < r_i+1 < |r_i|
...

It is the main property of Euclidean division that the inequalities on the right define uniquely r_i+1 from r_i-1 and r_i.

The computation stops when one reaches a remainder r_k+1 which is zero; the greatest common divisor is then the last non zero remainder r_k.

The extended Euclidean algorithm proceeds similarly, but adds two other sequences defined by

s₀=1, s₁=0
t₀=0, t₁=1
...
s_i+1=s_i-1-q_i s_i
t_i+1=t_i-1-q_i t_i

This should be easy to implement in Java, but the mathematical way it's expressed may make it hard to understand. I'll try to break it down.

Note that this is probably going to be easier to implement in a loop than recursively.

In the standard Euclidean algorithm, you compute r_i+1 in terms of r_i-1 and r_i. This means that you have to save the two previous versions of r. This part of the formula:

r_i+1=r_i-1-q_i r_i and 0 < r_i+1 < |r_i|
...

just means that r_i+1 will be the remainder when r_i-1 is divided by r_i. q_i is the quotient, which you don't use in the standard Euclidean algorithm, but you do use in the extended one. So Java code to perform the standard Euclidean algorithm (i.e. compute the GCD) might look like:

prevPrevR = a;
prevR = b;
while ([something]) {
    nextR = prevPrevR % prevR;
    quotient = prevPrevR / prevR;  // not used in the standard algorithm
    prevPrevR = prevR;
    prevR = nextR;
}

Thus, at any point, prevPrevR will be essentially r_i-1, and prevR will be r_i. The algorithm computes the next r, r_i+1, then shifts everything which in essence increments i by 1.

The extended Euclidean algorithm will be done the same way, saving two s values prevPrevS and prevS, and two t values prevPrevT and prevT. I'll let you work out the details.