BinaryLehmerGcd

A high-performance implementation of the greatest common divisor (GCD) algorithm that combines binary GCD with Lehmer's algorithm for optimal performance on large integers.

Overview

This library provides an efficient implementation of GCD computation that scales well from small integers to very large numbers. The algorithm uses different strategies based on the size of the input numbers:

• Small numbers ($\leq$ 32 bits): Uses standard binary GCD algorithm
• Large numbers ($>$ 32 bits): Applies Lehmer's reduction before binary GCD

Features

• High Performance: Optimized for large integers with $O(\log_2 n)$ time complexity
• Memory Efficient: $O(\log n)$ space complexity due to recursion
• Deterministic: Always produces the same result for the same inputs
• Well Documented: Comprehensive documentation with mathematical notation
• Production Ready: Thoroughly tested with randomized test cases

Installation

Add binary_lehmer_gcd to your list of dependencies in mix.exs:

def deps do
  [
    {:binary_lehmer_gcd, "~> 1.0"}
  ]
end

Usage

Basic Usage

iex> BinaryLehmerGcd.of(48, 18)
6

iex> BinaryLehmerGcd.of(0, 42)
42

iex> BinaryLehmerGcd.of(123456789, 987654321)
9

iex> BinaryLehmerGcd.of(2_147_483_647, 2_147_483_646)
1

Large Number Performance

The algorithm is particularly efficient for large integers:

# These large numbers are handled efficiently
iex> BinaryLehmerGcd.of(123456789012345678901234567890, 987654321098765432109876543210)
90

Algorithm Details

Binary GCD

The binary GCD algorithm is based on the following properties:

• $\gcd(0, b) = b$ and $\gcd(a, 0) = a$
• $\gcd(2a, 2b) = 2\gcd(a, b)$
• $\gcd(2a, b) = \gcd(a, b)$ when b is odd
• $\gcd(a, b) = \gcd(\frac{|a-b|}{2}, \min(a,b))$ when both a and b are odd

Lehmer's Algorithm

For large numbers, Lehmer's algorithm reduces the problem size by:

1. Taking the top digits of both numbers
2. Computing a linear combination that reduces the numbers
3. Applying this reduction to the original numbers
4. Continuing with binary GCD on the reduced numbers

Performance

• Time Complexity: $O(\log_2{n})$ for n-bit numbers
• Space Complexity: $O(\log n)$ due to recursion
• Optimizations:
  • Efficient trailing zero removal
  • Bit-level operations for speed
  • Division avoidance in Lehmer reduction
  • Early termination conditions

When to Use

This implementation is particularly beneficial when:

• Working with large integers (> 32 bits)
• Performance is critical
• You need deterministic results
• Memory usage should be minimized

Dependencies

This library depends on:

• BitLength - for efficient bit length computation
• TrailingZeros - for counting trailing zeros
• Bitwise - for bit-level operations

License

Copyright (c) 2025 University of Kitakyushu

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

References

• Lehmer, D.H. (1938). "Euclid's Algorithm for Large Numbers"
• Knuth, D.E. (1997). "The Art of Computer Programming, Volume 2"

Changelog

See CHANGELOG.md for a list of changes and version history.