#include "egcd.h"
/*Computes the coefficients of the smallest positive linear combination of two
integers _a and _b.
These are a solution (u,v) to the equation _a*u+_b*v==gcd(_a,_b).
_a: The first integer of which to compute the extended gcd.
_b: The second integer of which to compute the extended gcd.
_u: Returns the coefficient of _a in the smallest positive linear
combination.
_v: Returns the coefficient _of b in the smallest positive linear
combination.
Return: The non-negative gcd of _a and _b.
If _a and _b are both 0, then 0 is returned, though in reality the
gcd is undefined, as any integer, no matter how large, will divide 0
evenly.
_a*u+_b*v will not be positive in this case.
Note that the solution (u,v) of _a*u+_b*v==gcd(_a,_b) returned is not
unique.
(u+(_b/gcd(_a,_b))*k,v-(_a/gcd(_a,_b))*k) is also a solution for all
k.
The coefficients (u,v) might not be positive.*/
int egcd(int _a,int _b,int *_u,int *_v){
int a;
int b;
int s;
int t;
int u;
int v;
/*Make both arguments non-negative.
This forces the return value to be non-negative.*/
a=_a<0?-_a:_a;
b=_b<0?-_b:_b;
/*Simply use the extended Euclidean algorithm.*/
s=v=0;
t=u=1;
while(b){
int q;
int r;
int w;
q=a/b;
r=a%b;
a=b;
b=r;
w=s;
s=u-q*s;
u=w;
w=t;
t=v-q*t;
v=w;
}
/*u and v were computed for non-negative a and b.
If the arguments passed in were negative, flip the sign.*/
*_u=_a<0?-u:u;
*_v=_b<0?-v:v;
return a;
}