Euclidean algorithm

The Euclidean algorithm is one of the oldest numerical algorithms commonly used to solve the problem of computing the greatest 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))

Thanks 👍 for making it to the end 👨‍💻 and I really hope you found the content useful.

Leave a comment below or tweet me @ElishaChibueze if you have any questions or suggestions