Euclidean algorithm: the idea
Prerequisites: Whole numbers, divisibility, and remainders.
A common divisor divides both integers without a remainder. The greatest common divisor, or GCD, is the largest such positive integer. Dividing a by b gives a quotient q and remainder r: a = q × b + r. The common divisors of a and b are exactly those of b and r. Replacing (a, b) with (b, r) therefore preserves their GCD. When b reaches zero, a is the answer.
Try it
Try 252 and 105, then consecutive Fibonacci numbers such as 233 and 144. The latter require many small reductions. Try one zero input: the other number is immediately the answer.
Reading the display
The current pair appears as two blocks. The division history records a, b, q, and r; each next row replaces the pair with b and r.
Time and memory
O(log max(a,b)) remainder steps for positive inputs; O(1) stored integers. This treats bounded-integer arithmetic as constant cost.
The bounds above describe core work on prepared input. String conversion to code-point arrays and editor validation are additional work. The visualization saves the data at each operation so you can step backward. This recording requires extra time and memory beyond the algorithm’s own working storage. Input limits keep the demonstrations manageable.
When to use it—and what to watch
Useful for reducing fractions and checking whether numbers are coprime. Inputs here are nonnegative integers, not fractions. gcd(0,0) is conventionally returned as 0 in this implementation.
Continue exploring
- Extended Euclidean algorithm — Find a GCD and coefficients explaining how the inputs produce it.
- Sieve of Eratosthenes — Cross out multiples and reveal every prime up to a limit.
- Binary exponentiation — Build large powers by repeated squaring and halving.