From Euclid to Code: GCD Algorithm

In this article, we revisit Euclid’s algorithm for computing the Greatest Common Divisor (GCD)—an elegant method devised over 2,000 years ago that remains essential in modern computation, from cryptography to compiler internals.

Essence of GCD

Euclid didn’t work with numbers — he worked with lengths of lines, called magnitudes. His idea of finding the greatest common measure between two magnitudes was this:

If one line length doesn’t exactly measure the other, then subtract the smaller from the larger — and repeat the process with what’s left. Eventually, you'll reach a length that evenly measures the one before it. That length is the greatest common measure of both.

This process is guaranteed to terminate only if the two magnitudes are commensurable, i.e., their ratio is rational.

• The GCD of two numbers can be written as
  gcd(a,b)=gcd(b,a−b)

This approach is the foundation of Euclid’s GCD. Let’s try this out in code.

function gcd(a: number, b: number) {
  if (a === b) return a;

  if (a > b) return gcd(a-b, a)
  else return gcd(a, b-a)
}

we have a working algorithm with a worst case time complexity of O(max(a, b)). For large numbers, it performs poorly due to the sheer number of subtractions required.

Optimizing

There are some observations we can make to make this algorithm more efficient

Let’s say we’re computing gcd⁡(a,b) where a>b.

gcd(a, b) = gcd(a - b, b)

Now suppose instead of subtracting b once, we do it multiple times — until the remainder is less than b.

a = b*q + r, now if the GCD of a and b is say d then d divides a, b and r as well. From this we can postulate that gcd(a, b) = gcd(b, r) since the greatest element on the set of divisors is preserved as a > b > r.

Let’s see the code in action for this.

// recursive
function gcd(a: number, b: number) {
  if (b === 0) return a;
  return gcd(b, a % b)
}

// iterative
function gcd(a: number, b: number) {
 while (b !== 0) {
   [a, b] = [b, a % b]
 }
 return a
}

if you are wondering why we didn’t add a check for if a > b, thanks to the properties of modulo, the values get swapped automatically when needed, try it out 😉

For completeness, it's worth mentioning that there’s an even more optimized version of the GCD algorithm known as Stein’s Algorithm or Binary GCD

Unlike Euclid’s method, which uses division or modulo, Stein’s approach relies on bit-shifting and subtraction, making it well-suited for low-level systems or environments where division is expensive.

It’s particularly efficient when working with very large integers or inside performance-critical cryptographic routines. That said, for most high-level programming contexts, the standard modulo-based Euclidean algorithm is fast enough

🔑 Key Takeaways

• The original Euclid’s algorithm is based on repeated subtraction, using the identity:

  gcd⁡(a,b)=gcd⁡(b,a−b)

• The algorithm can be optimized using the modulo operation to skip repeated subtractions:

  gcd⁡(a,b)=gcd⁡(b,a mod b)

• Stein’s Binary GCD algorithm uses only bit shifts and subtraction, offering further optimization for large integers or environments where division is costly

📚 Further Reading

• From Mathematics to Generic Programming by Alexander A. Stepanov and Daniel E. Rose

💬 Feedback

If you’ve made it this far, thank you! I’d love to hear your thoughts on the article. If you have suggestions, corrections, or just want to chat — feel free to reach out or leave a comment.