Sign in to watch this lesson
Algorithms - Bits and Number Theory · 4:18
Euclid's Algorithm
The greatest common divisor through a picture: a 21 x 13 rectangle tiled greedily by squares 13, 8, 5, 3, 2, 1, 1, whose last square is the gcd, because subtracting the shorter side never changes it. The remainder does many cuts at once (gcd(45, 12) = 3 in three steps), consecutive Fibonacci numbers are the slowest inputs (Lamé's theorem: 85 steps at most up to 10^18, while a million random pairs on this Mac never needed more than 59), and the practical details: lcm as a / gcd * b to avoid overflow, negative remainders in C++, and Stein's binary GCD, which ran about 1.5 times faster than the % loop here.
You will learn
- Explain why gcd(a, b) = gcd(a - b, b) = gcd(b, a mod b), using the picture of a rectangle tiled by squares.
- Implement Euclid's algorithm with % (or use std::gcd / std::lcm) and compute lcm as a / gcd(a, b) * b without overflow.
- Bound the number of steps: consecutive Fibonacci numbers are the worst case (Lamé), so it is O(log min(a, b)), at most 85 steps for numbers up to 10^18.
- Describe Stein's binary GCD (factors of two, ctz, subtraction of odd numbers) and handle zeros and negative inputs.