git.ozlabs.org Git - ccan/blob - junkcode/tterribe@email.unc.edu-nmbrthry/egcd.c

   1 #include "egcd.h"
   2
   3 /*Computes the coefficients of the smallest positive linear combination of two
   4    integers _a and _b.
   5   These are a solution (u,v) to the equation _a*u+_b*v==gcd(_a,_b).
   6   _a: The first integer of which to compute the extended gcd.
   7   _b: The second integer of which to compute the extended gcd.
   8   _u: Returns the coefficient of _a in the smallest positive linear
   9        combination.
  10   _v: Returns the coefficient _of b in the smallest positive linear
  11        combination.
  12   Return: The non-negative gcd of _a and _b.
  13           If _a and _b are both 0, then 0 is returned, though in reality the
  14            gcd is undefined, as any integer, no matter how large, will divide 0
  15            evenly.
  16           _a*u+_b*v will not be positive in this case.
  17           Note that the solution (u,v) of _a*u+_b*v==gcd(_a,_b) returned is not
  18            unique.
  19           (u+(_b/gcd(_a,_b))*k,v-(_a/gcd(_a,_b))*k) is also a solution for all
  20            k.
  21           The coefficients (u,v) might not be positive.*/
  22 int egcd(int _a,int _b,int *_u,int *_v){
  23   int a;
  24   int b;
  25   int s;
  26   int t;
  27   int u;
  28   int v;
  29   /*Make both arguments non-negative.
  30     This forces the return value to be non-negative.*/
  31   a=_a<0?-_a:_a;
  32   b=_b<0?-_b:_b;
  33   /*Simply use the extended Euclidean algorithm.*/
  34   s=v=0;
  35   t=u=1;
  36   while(b){
  37     int q;
  38     int r;
  39     int w;
  40     q=a/b;
  41     r=a%b;
  42     a=b;
  43     b=r;
  44     w=s;
  45     s=u-q*s;
  46     u=w;
  47     w=t;
  48     t=v-q*t;
  49     v=w;
  50   }
  51   /*u and v were computed for non-negative a and b.
  52     If the arguments passed in were negative, flip the sign.*/
  53   *_u=_a<0?-u:u;
  54   *_v=_b<0?-v:v;
  55   return a;
  56 }