Implementation of the Lehmer GCD algorithm for computing the greatest common divisor of two non-negative integers.

The Lehmer GCD algorithm is particularly efficient for very large integers, using matrix operations to reduce the problem size while maintaining mathematical correctness. For smaller numbers (less than $2^{32}$), it falls back to the Binary GCD algorithm for optimal performance.

Algorithm Overview

The Lehmer algorithm works by:

1. Using the most significant bits of the input numbers to create a smaller problem
2. Solving this smaller problem using matrix operations
3. Using the solution to reduce the original problem size
4. Repeating until the numbers are small enough for direct computation

Examples

iex> LehmerGcd.of(48, 18)
6

iex> LehmerGcd.of(123456789, 987654321)
9

iex> LehmerGcd.of(0, 42)
42

iex> LehmerGcd.of(42, 0)
42

Performance

• For numbers smaller than $2^{32}$: Uses BinaryGcd for optimal performance
• For larger numbers: Uses Lehmer algorithm with $O(\log{n})$ complexity
• Memory usage: $O(1)$ additional space beyond input storage