//
// Euclid algorith for calculating of
// greatest common divisor of two integer numbers
//     d = gcd(a, b);
//
// Also the Extended Euclid algoritm is implemented
// that expresses the d = gcd(a, b) in the form
//     d = u*a + b*v

#include <stdio.h>
#include <assert.h>

int gcd(int a, int b);
int gcd1(int a, int b);
int extEucl(int a, int b, int* u, int* v);

int main() {
    int a, b;
    while (true) {
        printf("\nInput a, b:\n");
        scanf("%d%d", &a, &b);
        if (a == 0 && b == 0)
            break;

        printf("Calling recursive implementation\n");
        int d = gcd(a, b);
        printf("gcd = %d\n", d);

        printf("\nCalling iterative implementation\n");
        d = gcd1(a, b);
        printf("gcd = %d\n", d);

        printf("\nExtended Euclid algorithm:\n");
        int u, v;
        d = extEucl(a, b, &u, &v);
        printf(
            "gcd(%d, %d) = %d = %d*%d + %d*%d\n",
            a, b, d, u, a, v, b
        );
    }
    return 0;
}

int gcd(int a, int b) {
    printf("gcd(%d, %d)\n", a, b);
    if (b == 0)
        return a;

    int r = a % b;
    return gcd(b, r);
}

int gcd1(int a, int b) {
    printf("(%d, %d)\n", a, b);
    while (b != 0) {
        int r = a % b;
        a = b; b = r;
        printf("(%d, %d)\n", a, b);
    }
    return a;
}

int extEucl(int a, int b, int* u, int* v) {
    assert(a != 0 || b != 0);
    if (b == 0) {
        *u = 1; *v = 0;
        return a;
    }

    int q = a/b; int r = a%b;
    assert(a == q*b + r);
    // r == a - q*b; 
    int u1, v1;
    int d = extEucl(b, r, &u1, &v1);
    assert(d == u1*b + v1*r);
    // d = u1*b + v1*r = u1*b + v1(a - q*b) =
    //   = v1*a + (u1 - v1*q)*b
    *u = v1; *v = u1 - v1*q;
    return d;
}