fast gcd

1int gcd(int a, int b)
2{
3    if (a == 0)
4        return b;
5    return gcd(b % a, a);
6}
7 
8

1unsigned int gcd(unsigned int u, unsigned int v)
2{
3    int shift;
4    if (u == 0) return v;
5    if (v == 0) return u;
6    shift = __builtin_ctz(u | v);
7    u >>= __builtin_ctz(u);
8    do {
9        v >>= __builtin_ctz(v);
10        if (u > v) {
11            unsigned int t = v;
12            v = u;
13            u = t;
14        }  
15        v = v - u;
16    } while (v != 0);
17    return u << shift;
18}