+ 1

I'm trying to make a function for the extended euclidean algorithm, but the values of x and y never change

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

9th Jun 2017, 6:15 AM
Catalin Dervesteanu
Catalin Dervesteanu - avatar
4 odpowiedzi
+ 13
set x,y float or double and (double)(a/b)*y1
9th Jun 2017, 7:27 AM
Drinker
Drinker - avatar
+ 12
why u add x,y? try use that int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
9th Jun 2017, 7:09 AM
Drinker
Drinker - avatar
+ 1
looks like everything works now, with or without double, i quess my source was corrupted, thank you for help Drinker
9th Jun 2017, 7:34 AM
Catalin Dervesteanu
Catalin Dervesteanu - avatar
0
Well the extended version is all about finding x and y so that a*x+b*y=gcd (a,b)
9th Jun 2017, 7:15 AM
Catalin Dervesteanu
Catalin Dervesteanu - avatar