Summary of the three Euclidean Algorithms for computing GCD

euclidean-algorithm.md

Euclidean algorithm

The Euclidean algorithm is one of the oldest numerical algorithms commonly used to solve the problem of computing the greated common divisor (gcd) of two positive integers.

There are three main implementations of the Euclidean algorithm:

1. Euclidean algorithm by subtraction

Here, we recursively subtract the smaller number from the larger number

/**
 * Recursively subtract the smaller number from the larger number
 * until the two numbers are equal
 *
 * @param {number} a
 * @param {number} b
 */
const gcd = (a, b) => {
  if (a === b) return a;

  if (a > b) return gcd(a - b, b);

  return gcd(a, b - a);
};

The time complexity of the above algorithm is O(a+b) which is linear

2. Euclidean algorithm by division

Here, we use a form of division by to recursively compute the gcd

/**
 * Recursively compute the gcd using some form of division
 *
 * @param {number} a
 * @param {number} b
 */
const gcd = (a, b) => {
  if (a % b === 0) return b;

  return gcd(b, a % b);
};

The time complexity of the above algorithm is logarithmic with O(log(a+b))

3. Binary Euclidean algorithm

/**
 * Recursively compute the gcd using some binary operations
 *
 * @param {number} a
 * @param {number} b
 */
const gcd = (a, b, r = 1) => {
  if (a === b) return r * a;

  if (a % 2 === 0 && b % 2 === 0)
    return gcd(Math.floor(a / 2), Math.floor(b / 2), 2 * r);

  if (a % 2 === 0) return gcd(Math.floor(a / 2), b, r);

  if (b % 2 === 0) return gcd(a, Math.floor(b / 2), r);

  if (a > b) return gcd(a - b, b, r);

  return gcd(a, b - a, r);
};

This one has a time complexity of O(log(a) + log(b))