071: GCD and LCM

Difficulty: ⭐ Level: Foundations Compute greatest common divisor and least common multiple — the Euclidean algorithm is 2300 years old and fits in one line of Rust.

The Problem This Solves

You need to simplify fractions, find the scheduling period for two recurring events, or reduce a set of numbers to their common factor. These all reduce to GCD and LCM. The brute-force approach tries every number from 1 up to `min(a, b)`. That's O(n) and slow for large inputs. Euclid's algorithm is O(log n) and looks almost magical: `gcd(a, b) = gcd(b, a mod b)`. The modulo repeatedly reduces the problem until one number becomes 0. Both OCaml and Rust express this in nearly identical code. The algorithm itself is the lesson — the language just gets out of the way.

The Intuition

Why does `gcd(a, b) = gcd(b, a % b)` work? Because any common divisor of `a` and `b` must also divide `a - b`, `a - 2b`, ..., and `a mod b`. So the set of common divisors doesn't change when you replace `a` with `a mod b`. You keep reducing until one number is 0, at which point the other number is the GCD. LCM follows from a simple identity: `lcm(a, b) = a * b / gcd(a, b)`. Divide before multiplying to avoid integer overflow. For lists of numbers, fold the binary GCD/LCM across the list: `gcd(a, gcd(b, gcd(c, d)))`.

How It Works in Rust

// Euclid's algorithm — clean recursion
pub fn gcd(a: u64, b: u64) -> u64 {
 if b == 0 { a } else { gcd(b, a % b) }
}

// LCM via GCD identity — divide first to prevent overflow
pub fn lcm(a: u64, b: u64) -> u64 {
 if a == 0 || b == 0 { 0 }
 else { a / gcd(a, b) * b }
}

// GCD of a whole list — fold with reduce
pub fn gcd_list(nums: &[u64]) -> u64 {
 nums.iter().copied().reduce(gcd).unwrap_or(0)
}

// LCM of a list — same pattern
pub fn lcm_list(nums: &[u64]) -> u64 {
 nums.iter().copied().reduce(lcm).unwrap_or(0)
}

`reduce()` is like `fold()` but uses the first element as the initial accumulator. Returns `None` for empty slices — `unwrap_or(0)` handles that.

What This Unlocks

Fraction arithmetic — simplify `a/b + c/d` by computing LCM of denominators
Scheduling — find when two periodic events next coincide (LCM of their periods)
Number theory — GCD is the foundation of modular arithmetic, RSA encryption, and more

Key Differences

Concept	OCaml	Rust
Recursive GCD	`let rec gcd a b = if b = 0 then a else gcd b (a mod b)`	Identical structure
LCM	`abs (a b) / gcd a b`	`a / gcd(a, b) b` (divide first)
List GCD	`List.fold_left gcd h t`	`.reduce(gcd).unwrap_or(0)`
Tail recursion	OCaml optimizes automatically	Rust may stack-overflow on huge inputs; use iterative version

/// # GCD and LCM — Euclidean Algorithm
///
/// Classic recursive algorithm, beautifully concise in both OCaml and Rust.

/// Recursive GCD using Euclid's algorithm.
/// Rust's pattern matching and tail recursion make this elegant.
pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 { a } else { gcd(b, a % b) }
}

/// LCM using the GCD identity: lcm(a,b) = |a*b| / gcd(a,b)
pub fn lcm(a: u64, b: u64) -> u64 {
    if a == 0 || b == 0 {
        0
    } else {
        a / gcd(a, b) * b // divide first to avoid overflow
    }
}

/// GCD of a list using fold
pub fn gcd_list(nums: &[u64]) -> u64 {
    nums.iter().copied().reduce(gcd).unwrap_or(0)
}

/// LCM of a list
pub fn lcm_list(nums: &[u64]) -> u64 {
    nums.iter().copied().reduce(lcm).unwrap_or(0)
}

/// Iterative GCD (avoids potential stack overflow for very large inputs)
pub fn gcd_iterative(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let temp = b;
        b = a % b;
        a = temp;
    }
    a
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(48, 18), 6);
        assert_eq!(gcd(100, 75), 25);
        assert_eq!(gcd(17, 13), 1); // coprime
    }

    #[test]
    fn test_gcd_with_zero() {
        assert_eq!(gcd(5, 0), 5);
        assert_eq!(gcd(0, 5), 5);
    }

    #[test]
    fn test_lcm() {
        assert_eq!(lcm(12, 18), 36);
        assert_eq!(lcm(4, 6), 12);
    }

    #[test]
    fn test_lcm_zero() {
        assert_eq!(lcm(0, 5), 0);
    }

    #[test]
    fn test_gcd_list() {
        assert_eq!(gcd_list(&[48, 36, 60, 12]), 12);
    }

    #[test]
    fn test_gcd_list_empty() {
        assert_eq!(gcd_list(&[]), 0);
    }

    #[test]
    fn test_lcm_list() {
        assert_eq!(lcm_list(&[2, 3, 4, 5]), 60);
    }

    #[test]
    fn test_iterative_matches_recursive() {
        assert_eq!(gcd(48, 18), gcd_iterative(48, 18));
        assert_eq!(gcd(100, 75), gcd_iterative(100, 75));
    }
}

fn main() {
    println!("{:?}", gcd(48, 18), 6);
    println!("{:?}", gcd(100, 75), 25);
    println!("{:?}", gcd(17, 13), 1);
}

(* GCD and LCM — Euclidean Algorithm *)

let rec gcd a b = if b = 0 then a else gcd b (a mod b)
let lcm a b = if a = 0 || b = 0 then 0 else abs (a * b) / gcd a b

let gcd_list = function
  | [] -> 0
  | h :: t -> List.fold_left gcd h t

let () =
  Printf.printf "gcd(48,18) = %d\n" (gcd 48 18);
  Printf.printf "lcm(12,18) = %d\n" (lcm 12 18);
  Printf.printf "gcd_list = %d\n" (gcd_list [48; 36; 60; 12]);
  assert (gcd 48 18 = 6);
  assert (lcm 12 18 = 36);
  assert (gcd_list [48; 36; 60; 12] = 12);
  Printf.printf "All GCD/LCM tests passed!\n"

📊 Detailed Comparison

GCD and LCM — OCaml vs Rust Comparison

Core Insight

Euclid's algorithm is one of the oldest algorithms and maps perfectly to both languages. The recursive version is nearly character-for-character identical. The interesting differences emerge in the list version and overflow handling.

OCaml Approach

`let rec gcd a b = if b = 0 then a else gcd b (a mod b)` — one line, crystal clear. The list version uses `List.fold_left gcd h t` with pattern matching to handle the empty list. OCaml's arbitrary-precision integers (via Zarith) can avoid overflow entirely.

Rust Approach

`fn gcd(a: u64, b: u64) -> u64` — similarly concise. The list version uses `Iterator::reduce()` which returns `Option<T>` (handling the empty case). For LCM, we divide before multiplying (`a / gcd(a,b) * b`) to avoid intermediate overflow — a detail OCaml programmers often ignore due to big integers.

Comparison Table

Aspect	OCaml	Rust
Memory	Stack frames (recursive)	Stack frames or iterative
Null safety	Pattern match on list	`Option` from `reduce()`
Errors	`abs` handles negatives	`u64` — no negatives to handle
Iteration	`fold_left` on list	`reduce()` on iterator
Overflow	Use Zarith for safety	Must divide-before-multiply

Things Rust Learners Should Notice

1. `reduce()` vs `fold()` — reduce uses the first element as init, returns `Option`; fold takes explicit init 2. Overflow prevention — `a / gcd(a,b) b` avoids the `a b` overflow that `lcm` could hit 3. `u64` means no negatives — simpler than OCaml's signed `int`, but requires type choice upfront 4. Tail recursion not guaranteed — Rust doesn't guarantee TCO; the iterative version is safer for huge inputs 5. `.copied()` — converts `&u64` to `u64` in the iterator chain (like OCaml's implicit value semantics)