/Java/Extended euclidean algorithm in java

Extended euclidean algorithm in java

Extended euclidean algorithm

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

Source: cp-algorithms.com

Extended euclidean algorithm in java

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
    }
}
}

Source: stackoverflow.com

Similar codes

4 votes264 views3 answers
Online currency rate api
Java
0 vote244 views1 answer
Java resultset.absolute
Java
0 vote254 views1 answer
Rotate Vector by an angle
Java
6 votes271 views2 answers
Get absolute path from relative java
Java
1 vote302 views1 answer
Spring mvc project example
Java Spring
1 vote292 views1 answer
Long vs int java
Java
0 vote245 views1 answer
Super class java
Java
0 vote272 views1 answer
Android generate random int
Java
0 vote281 views1 answer
Unprocessed continuation reference(s) remaining name
Java
0 vote275 views1 answer
Convert character digit to int java
Java