Lair Of The Multimedia Guru

How do we find the greatest common divisor of 2 integers? Try all integers which are ≤ then the arguments and select the largest which divides both with no remainder, works but its too slow. Or maybe factorize both, take the common factors and multiply them together like they probably told you in school, but thats still far too slow for anything but the small numbers in school excercies

A more reasonable algorithm is Euclid’s algorithm

int gcd(int a, int b) {
  while (b != 0) {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}

which on a P3 needs about 631 cpu cycles with test numbers generated by rand() % 100000000+1
for a trivial proof why euclids algorithm works, see the wikipedia link above
Yet another one is the Binary GCD algorithm

 unsigned int gcd(unsigned int u, unsigned int v) {
     unsigned int k = 0;
     if (u == 0)
         return v;
     if (v == 0)
         return u;
     while ((u & 1) == 0  &&  (v & 1) == 0) { /* while both u and v are even */
         u >>= 1;   /* shift u right, dividing it by 2 */
         v >>= 1;   /* shift v right, dividing it by 2 */
         k++;       /* add a power of 2 to the final result */
     }
     /* At this point either u or v (or both) is odd */
     do {
         if ((u & 1) == 0)      /* if u is even */
             u  >>= 1;           /* divide u by 2 */
         else if ((v &  1) == 0) /* else if v is even */
             v  >>= 1;           /* divide v by 2 */
         else if (u >= v)       /* u and v are both odd */
             u = (u-v) >> 1;
         else                   /* u and v both odd, v > u */
             v = (v-u) >> 1;
     } while (u > 0);
     return v << k;  /* returns v * 2^k */
 }

which for the same numbers needed 544 cpu cycles on average and

int gcd(int a, int b){
    int i,j;
    for(i=0; !(a&1); i++)
        a>>=1;
    for(j=0; !(b&1); j++)
        b>>=1;

    while(b!=a){
        b-= a;
        if(b<0){
            a+= b;
            b= -b;
        }
        while(!(b&1))
            b>>=1;
    }
    return a<<FFMIN(i,j);
}

which is a different implementtion of the binary gcd algo, was laying around in my home directory and needs about 504 cycles