gcd.c:

/* Greatest Common Divisor */
long gcd (x,y) long x,y; {
  long temp;
  long g;

  if (x < y) { temp = x; x = y; y = temp; }

  g = 0;
  while ((0 == (x & 1)) && (0 == (y & 1))) { /* While both even */ 
    x >>= 1; y >>= 1; g++;
  }
  while (x != 0) {
     while (0 == (x & 1)) { x >>= 1; }
     while (0 == (y & 1)) { y >>= 1; }
     temp = (x-y)/2; if (temp<0) { temp = -temp; }
     if (x >= y) {
        x = temp;
     } else {
        y = temp;
     }
  }
  return y<<g;
}

Go to ...

• Factoring Page
• John Halleck's Home Page

This page is http://www.cc.utah.edu/~nahaj/factoring/gcd.c.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on January 12th, 2009
And the underlying file was last modified on December 12th, 2005