Hii everyone,
I am trying to write the java code of extended euclidan algorithm but couldn’t write it, I also try to search on internet but there is no stuff for java …
If anyone can help me, please share your code Or opinion.
Hii everyone,
I am trying to write the java code of extended euclidan algorithm but couldn’t write it, I also try to search on internet but there is no stuff for java …
If anyone can help me, please share your code Or opinion.
Here you go, the math should be clear from the equation in comments.
Feel free to ask. Also, I wrote it just now, I’d suggest testing on couple of inputs. Plus It might overflow when dealing with large numbers.
static int[] extendedGCD(int a, int b) throws Exception{
if(a == 0 || b == 0){
//assert(a+b == 1)
if(a == 0)return new int[]{0, 1};
else return new int[]{1, 0};
}
int[] ext = extendedGCD(b, a%b);
//a*x+b*y = 1, assuming a > b, though it works for a <= b too, just k = 0
//a = k*b+m, k = floor(a/b)
//(k*b+m)*x+b*y = 1
//m*x + b*(k*b+y) = 1
//ext[0] = k*b+y, ext[1] = x, retrieve x and y
int oldX = ext[1], oldY = ext[0];
int k = a/b;
int newX = oldX, newY = oldY-k*oldX;
hold(a*newX + b*newY == 1);
return new int[]{newX, newY};
}
Taran i have a code in c++ which uses class and with the help of it , it was returning three value x, y, gcd
Can we make a java code for the same