GCD and the magic of subtraction
I usually use this algorithm (in C-like syntax) with modulo division:<p>int gcd(int a, int b)
{
    while (b != 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}<p>I think it is a rather efficient algorithm because it only has one test, one operation and two assignments. A good optimizing compiler could turn the loop in four instructions.