New junkcode from Tim.

[ccan] / junkcode / tterribe@email.unc.edu-nmbrthry / egcd.c

diff --git a/junkcode/tterribe@email.unc.edu-nmbrthry/egcd.c b/junkcode/tterribe@email.unc.edu-nmbrthry/egcd.c
new file mode 100644 (file)
index 0000000..11eea58
--- /dev/null
+++ b/junkcode/tterribe@email.unc.edu-nmbrthry/egcd.c
@@ -0,0 +1,56 @@
+#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;
+}