Forem

King Elisha
King Elisha

Posted on

Euclidean algorithm

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);
};
Enter fullscreen mode Exit fullscreen mode

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);
};
Enter fullscreen mode Exit fullscreen mode

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);
};
Enter fullscreen mode Exit fullscreen mode

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More