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

   1 #if !defined(_egcd_H)
   2 # define _egcd_H (1)
   3
   4 /*Computes the coefficients of the smallest positive linear combination of two
   5    integers _a and _b.
   6   These are a solution (u,v) to the equation _a*u+_b*v==gcd(_a,_b).
   7   _a: The first integer of which to compute the extended gcd.
   8   _b: The second integer of which to compute the extended gcd.
   9   _u: Returns the coefficient of _a in the smallest positive linear
  10        combination.
  11   _v: Returns the coefficient _of b in the smallest positive linear
  12        combination.
  13   Return: The non-negative gcd of _a and _b.
  14           If _a and _b are both 0, then 0 is returned, though in reality the
  15            gcd is undefined, as any integer, no matter how large, will divide 0
  16            evenly.
  17           _a*u+_b*v will not be positive in this case.
  18           Note that the solution (u,v) of _a*u+_b*v==gcd(_a,_b) returned is not
  19            unique.
  20           (u+(_b/gcd(_a,_b))*k,v-(_a/gcd(_a,_b))*k) is also a solution for all
  21            k.
  22           The coefficients (u,v) might not be positive.*/
  23 int egcd(int _a,int _b,int *_u,int *_v);
  24
  25 #endif