Euclid's GCD

O(log min(a, b))

Euclid's algorithm finds the greatest common divisor without any factoring. Picture an a×b rectangle. Cut off as many b×b squares as fit along the long side — that's ⌊a/b⌋ of them — and you're left with a smaller (a mod b)×b strip. The GCD of the original rectangle is the same as the GCD of that strip, so repeat on it, and again, until a side divides the other exactly. The very last square you carve is the largest square that tiles the whole rectangle, and its side is gcd(a, b). Each carving step is exactly the arithmetic gcd(a, b) = gcd(b, a mod b), so the picture and the algorithm are the same thing. It runs in O(log min(a, b)) steps — the rectangle shrinks fast, the same reason the Fibonacci pair is the worst case.

Rectangle tiling
Edit the input and press Play

How it works

  1. Lay out the two numbers as the sides of a rectangle.
  2. Carve off as many squares of the shorter side as fit.
  3. Recurse on the leftover strip — gcd(a, b) = gcd(b, a mod b).
  4. Stop when nothing is left; the last square's side is the GCD.

Pseudocode

1gcd(a, b):                          # O(log min(a, b))2  # geometrically: tile an a×b rectangle with squares3  while b ≠ 0:4    # carve ⌊a/b⌋ squares of side b off the rectangle5    a, b ← b, a mod b                # leftover strip recurses6  return a                           # side of the last square