Euclid’s GCD Algorithm:

• Fundamentals:
  • gcd(N, M) = gcd(M, N mod M)
  • gcd(N, 0) = N
• Implementation in C:

int Euclid_gcd_recursive(int a, int b)
{
  if (b == 0)
    return a;
  return Euclid_gcd_recursive(b, a % b);
}

int Euclid_gcd_iterative(int a, int b)
{
  int t;
  while (b) {
    a = b;
    b = t % b;
  }
  return a;
}

• Complexity: O(lg(min{a, b})) arithmetic operations.

Stein’s GCD Algorithm:

• Fundamentals:
  • gcd(N, M) = 2*gcd(N/2, M/2), both N and M are even
  • gcd(N, M) = gcd(N/2, M), N is even but M is odd
  • gcd(N, M) = gcd(N, N-M), both N and M are odd
  • gcd(N, 0) = N
• Advantages: only uses additions, subtractions and bit-shift operations.
• Implementation in C:

int Stein_gcd(int a, int b)
{
  int t, c = 1;
  if (a < b) {
    t = a;
    a = b;
    b = t;
  }
  while (b) {
    if (a % 2) {
      if (b % 2) {
        a -= b;
      }
      else {
        b >>= 1;
      }
    }
    else if (b % 2) {
      a >>= 1;
    }
    else {
      c <<= 1;
      a >>= 1;
      b >>= 1;
    }

    if (a < b) {
      t = a;
      a = b;
      b = t;
    }
  }
  return a * c;
}

• Complexity:

Extensions:

1. Given integers a and b, a slight extension of Euclid's gcd algorithm enables us to find integers x and y
   ax + by = gcd(a, b)
2. One step further, we can find intergers u and v
   au + bv = 0

   or

   |au| = |bv| = lcm(a, b)

Example 1: a = 51, b = 21

51 = 2 * 21 + 9	9 = 51 - 2 * 21
21 = 2 * 9 + 3	3 = 21 - 2 * 9 = 21 - 2 * (51 - 2 * 21) = -2 * 51 + 5 * 21
9 = 3 * 3 + 0	0 = 9 - 3 * 3 = 51 - 2 * 21 - 3 * (-2 * 51 + 5 * 21) = 7 * 51 - 17 * 21

Thus x = -2, y = 5 works, and gcd(51, 21) = 3;
u = 7, v = -17 works, and lcm(51, 21) = 51 * 7 = 21 * 17 = 357.
Example 2: a = 101, b = 12

101 = 8 * 12 + 5	5 = 101 - 8 * 12
12 = 2 * 5 + 2	2 = 12 - 2 * 5 = 12 - 2 * (101 - 8 * 12) = -2 * 101 + 17 * 12
5 = 2 * 2 + 1	1 = 5 - 2 * 2 = 101 - 8 * 12 - 2 * (-2 * 101 + 17 * 12) = 5 * 101 - 42 * 12
2 = 2 * 1 + 0	0 = 2 - 2 * 1 = -2 * 101 + 17 * 12 - 2 * (5 * 101 - 42 * 12) = -12 * 101 + 101 * 12

Thus x = 5, y = -42 works, and gcd(101, 12) = 1;
u = -12, v = 101, and lcm(101, 12) = 12 * 101 = 1212.

3. From the second extension, it can be deduced by replacing all minus by plus in the second column that
   |au| + |bv| = 2*lcm(a, b)

   Thus, we've got an lcm algorithm derived from Euclid's gcd algorithm.

Euclid-based LCM Algorithm:

• Fundamentals: the process of Euclid's GCD algorithm.

• Implementation in C:

int lcm(int a, int b)
{
  int t;
  int u, v;
  if (a < b) {
    t = a;
    a = b;
    b = t;
  }

  u = a;
  v = b;

  while (b) {
    u += a / b * v;
    t = u;
    u = v;
    v = t;
    t = a;
    a = b;
    b = t % b;
  }
  return v / 2;
}

• Complexity: O(lg(min{a, b})) arithmetic operations.

Variant of Euclid-based LCM Algorithm:

• Fundamentals: divisions and modulo operations are decayed to subtractions, while multiplications are decayed to additions.
• Advandages: only uses additions and subtractions.
• Implementation in C:

int lcm(int a, int b)
{
  int u = a, v = b;

  while (a != b) {
    if (a > b) {
      a -= b;
      u += v;
    }
    else {
      b -= a;
      v += u;
    }
  }
  return (u + v) / 2;
}

• Complexity: