Theory

Consider gcd(a, b), let's say a > b, then we have:

gcd(a, b) == gcd(a - b, b)

Proof

Consider gcd(a, b) == x, a > b, and let's say:

a = x * k1
b = x * k2

Then:

a - b = x * (k1 - k2)
      = x * k3

Where k3 > 0. This means a - b and b must have x as common divisor.

Now we need to proof x is the greatest common divisor of a - b and b. Consider:

gcd(a - b, b) = y

If y > x, let's say:

a - b = y * k3
    b = y * k4

Then we have:

a = (a - b) + b
  = y * (k3 + k4)

Then gcd(a, b) == x will be false, because in this case, y > x, and both a and b have factor y, so gcd(a, b) == y. Contradict.

Optimization

Since gcd(a, b) == gcd(a - b, b), when:

• a > b
• a % b > 0

we have:

gcd(a, b) = gcd(a - b - b - ... - b, b)
          = gcd(a % b, b)

Based on this conclusion, we could calculate gcd(a, b) in a recursive way.

Code

#include "../general.h"

using gcdnum_t = unsigned long long;

void swap(gcdnum_t &a, gcdnum_t &b)
{
    auto tmp = a;
    a = b;
    b = tmp;
}

gcdnum_t calc_gcd(gcdnum_t a, gcdnum_t b)
{
    if (a <= 0 || b <= 0)
    {
        cout << "Input number should be positive" << endl;
        exit(-1);
    }
    // ensure a is always larger
    if (a < b)
    {
        swap(a, b);
    }
    cout << format("Calculate gcd({:>3}, {:>3})\n", a, b);

    // get mod
    auto mod = a % b;

    // if mod zero, smaller number is the gcd
    if (mod == 0)
    {
        return b;
    }
    // else, calc recursively
    return calc_gcd(b, mod);
}

int main()
{
    while (true)
    {
        gcdnum_t a, b;
        cout << "Enter two numbers: ";
        cin >> a >> b;
        if (a == 0 && b == 0)
        {
            return 0;
        }
        cout << calc_gcd(a, b) << endl;
    }
}