Euclidean Algorithm and Runtime

The Euclidean algorithm calculates the greatest common divisor (GCD) of a and b. The modulo variant replaces the pair (a, b) with (b, a mod b) until the remainder is 0. Then, the current value of b is the GCD.

Example: GCD(92, 32): 92 = 2*32 + 28, continue with (32, 28), (28, 4), (4, 0). Result 4.

For consecutive Fibonacci numbers, the modulo variant is significantly more efficient than repeated subtraction: the number of steps grows only slowly (logarithmically) with the size of the numbers. The subtraction variant can require a linear number of steps.

The algorithm is deterministic: the same inputs yield the same GCD.

$$\gcd(a,b)=\gcd(b,a \bmod b)$$

Where used

Building block in cryptography (modular inverse, RSA preparation), fraction reduction, aligning clock/sample rates, lattice and number theory code. The logarithmic number of steps is the reason why GCD remains practical even for large integers.

Depth

The algorithm is based on the invariant GCD(a, b) = GCD(b, a mod b). Each step replaces the pair with a smaller equivalent problem. Once the second value is zero, the first contains the desired divisor.

In the worst case, the remainder can shrink only slowly. The slowest sequences are closely related to consecutive Fibonacci numbers. Nevertheless, the number of steps grows only proportionally to the number of digits in the input and not proportionally to their numeric value.

The iterative form requires constant additional memory. The recursive form represents the same state sequence in the call stack and is mathematically concise, but offers no automatic memory advantage in Java.

Difficulty levels

1. Execute remainder steps for two positive numbers.
2. Justify the GCD invariant using division with remainder.
3. Explain the Fibonacci connection for unfavorable inputs.

Pitfalls

A common mistake is confusing the quotient and remainder. For negative inputs or a = b = 0, it must also be established which preconditions and sign conventions are in effect.