It is better to implement a binary version of the Euclidean algorithm. It has a smaller constant hidden in the O (log (n)) record, because dividing by 2 is much faster than taking the remainder on modern processors.

A little longer, but a little faster, since without recursion.

 int gcd(int a,int b) { while(a && b) { int c=a%b; a=b; b=c; } return a | b; } 

I constantly write like this:

 int gcd(const int &a, const int &b){return a ? gcd(b%a, a) : b;} 

Experiment

It became interesting whether the division is really so bad and how much it affects the performance. Made a small "benchmark":

 #include <stdio.h> #include <sys/time.h> /** * Different implementations of GCD algorithm */ int gcd(const int a, const int b) { return a ? gcd(b%a, a) : b; } int iterable_gcd(int a, int b) { int t; while (a) t = a, a = b % a, b = t; return b; } int cycled_gcd(int a, int b) { for (;;) { a %= b; if (!a) return b; b %= a; if (!b) return a; } } int binary_gcd(int u, int v) { int shift, t; if (u == 0) return v; if (v == 0) return u; for (shift = 0; ((u | v) & 1) == 0; ++shift) { u >>= 1; v >>= 1; } while ((u & 1) == 0) u >>= 1; do { while ((v & 1) == 0) v >>= 1; if (u > v) t = v, v = u, u = t; v = v - u; } while (v != 0); return u << shift; } /** * Timers */ void timeit(int (*implementation)(int, int), const int from, const int to) { int i, j; struct timeval tv1, tv2; gettimeofday(&tv1, NULL); for (i = from; i < to; ++i) { for (j = from; j < to; ++j) { implementation(i, j); } } gettimeofday(&tv2, NULL); printf("Total time = %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec) / 1000000 + (double) (tv2.tv_sec - tv1.tv_sec) ); } void timeit_small_numbers(int (*implementation)(int, int)) { const int from = 1000, to = from + 9*1000; timeit(implementation, from, to); } void timeit_big_numbers(int (*implementation)(int, int)) { const int from = 1000*1000*1000, to = from + 9*1000; timeit(implementation, from, to); } int main(int argc, char *argv[]) { int (*implementations[])(int,int) = { cycled_gcd, gcd, iterable_gcd, binary_gcd }; const int size = sizeof(implementations) / sizeof(implementations[0]); for (int i = 0; i < size; ++i) timeit_small_numbers(implementations[i]); for (int i = 0; i < size; ++i) timeit_big_numbers(implementations[i]); return 0; } 

• gcd - it is easy to remember the implementation is easy to implement.
• cycled_gcd - was proposed in one of the answers, but it is sometimes even worse for gcd .
• iterable_gcd - recursion can impose its own time expenses, therefore added an iterative option, but the -O3 flag does the work, or the costs are very small
• binary_gcd - based on wiki code

If we take numbers from 1000 to 10 * 1000 and from billion to billion + 9 * 1000, we will have different results.

 $ gcc -O3 run.c -o run $ ./run Test on small numbers Total time = 8.311910 seconds Total time = 8.329916 seconds Total time = 8.333715 seconds Total time = 7.837158 seconds Test on big numbers Total time = 10.425167 seconds Total time = 10.481676 seconds Total time = 10.460748 seconds Total time = 17.428999 seconds 

At low numbers binary_gcd almost 7% faster than any of the implementations. This is a very good result. If of course you are sure that you will not have large numbers. Why?

Because on large numbers binary_gcd quickly degrades and already shows 67% more working time than other implementations.

Conclusion

Fission-based implementations do not degrade so quickly, although they are inferior in performance at small numbers.