# 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`:

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

## Usage

### Basic Usage

```elixir
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:

```elixir
# 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](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](CHANGELOG.md) for a list of changes and version history.