// // 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 #include 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; }