Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Extended Euclidean Algorithm (with complete output)
//This is how the output looks
i g s u v
0 9692 0 1 0
1 360 26 0 1
2 332 1 1 -26
3 28 11 -1 27
4 24 1 12 -323
5 4 6 -13 350
ggt(9692,360)=4 =(-13*9692)+(350*360)
public class SomeMath {
public static int extendedEuclideanAlgorithm(int a, int b) {
ArrayList<Integer> g = new ArrayList<>();
g.add(Math.max(a, b));
g.add(Math.min(a, b));
ArrayList<Integer> s = new ArrayList<>();
s.add(0);
ArrayList<Integer> u = new ArrayList<>();
u.add(1);
u.add(0);
ArrayList<Integer> v = new ArrayList<>();
v.add(0);
v.add(1);
int i = 1;
while (g.get(i) != 0) {
s.add(Math.floorDiv(g.get(i - 1), g.get(i)));
g.add(Math.floorMod(g.get(i - 1), g.get(i)));
u.add(u.get(i - 1) - (u.get(i) * s.get(i)));
v.add(v.get(i - 1) - (v.get(i) * s.get(i)));
i++;
}
printTable(i,g,s,u,v);
String ggt=String.format("ggt(%d,%d)=%d",g.get(0),g.get(1),g.get(i-1));
String bezout=String.format("(%d*%d)+(%d*%d)",u.get(i-1),g.get(0),v.get(i-1),g.get(1));
System.out.println(ggt+" ="+bezout);
return g.get(i - 1);
}
private static void printTable(int imax,ArrayList<Integer> g,ArrayList<Integer> s,ArrayList<Integer> u,ArrayList<Integer> v) {
System.out.println(String.format("%5s%5s%5s%5s%5s","i","g","s","u","v"));
for (int i = 1; i <= imax; i++) {
System.out.println(String.format("%5d%5d%5d%5d%5d", i-1, g.get(i-1), s.get(i-1), u.get(i-1), v.get(i-1)));
}
System.out.println("\n\n");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.