076: GCD and LCM — Euclidean Algorithm

Difficulty: 2 Level: Beginner Recursive Euclidean GCD, derived LCM, and fold-based variants for sequences — pure math with `Copy` types.

The Problem This Solves

Finding the greatest common divisor and least common multiple are fundamental number theory operations — used in fraction reduction, scheduling (find a common period), cryptography, and anywhere you need to simplify ratios. The Euclidean algorithm is also the canonical example of a pure recursive algorithm with no ownership complexity: integers are `Copy`, no heap allocation, and the recursive structure maps 1:1 from OCaml to Rust with zero changes to the logic.

The Intuition

The Euclidean algorithm: `gcd(a, 0) = a`, `gcd(a, b) = gcd(b, a % b)`. That's it. Each call reduces the problem: `gcd(48, 18)` → `gcd(18, 12)` → `gcd(12, 6)` → `gcd(6, 0)` = 6. LCM follows from GCD: `lcm(a, b) = a / gcd(a, b) * b`. The division before multiplication avoids overflow — divide first to reduce the magnitude, then multiply. For a list: fold with `gcd` as the combining function. `gcd_list([12, 18, 24]) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6`.

How It Works in Rust

// Euclidean algorithm — integers are Copy, so ownership is trivial
pub fn gcd(a: u64, b: u64) -> u64 {
 if b == 0 { a } else { gcd(b, a % b) }
}

// LCM via GCD — 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 slice — fold pattern: OCaml's List.fold_left gcd 0
pub fn gcd_list(nums: &[u64]) -> u64 {
 nums.iter().copied().reduce(gcd).unwrap_or(0)
 //          ^^^^^^ Copy out each &u64 so we pass u64 to gcd directly
 //                              ^^^^^^ reduce = fold without initial value
}

// Accept any iterable — more flexible signature
pub fn gcd_iter(nums: impl IntoIterator<Item = u64>) -> u64 {
 nums.into_iter().reduce(gcd).unwrap_or(0)
}

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

`.copied()` on an iterator of `&u64` turns `Option<&u64>` into `Option<u64>` — necessary because `gcd` takes `u64`, not `&u64`. With `Copy` types, `.copied()` is idiomatic and free. `.reduce()` is like `.fold()` but uses the first element as the initial accumulator — appropriate when there's no sensible default (what's `gcd` of an empty list? We use 0 as a convention).

What This Unlocks

Fraction simplification: `Fraction { num / gcd(num, den), den / gcd(num, den) }`.
Scheduling: LCM of periods gives the first time all periodic events coincide.
Modular arithmetic: GCD tells you if `ax ≡ b (mod n)` has a solution.

Key Differences

Concept	OCaml	Rust
Recursive GCD	`let rec gcd a b = if b = 0 then a else gcd b (a mod b)`	`fn gcd(a: u64, b: u64) -> u64 { if b == 0 { a } else { gcd(b, a % b) } }`
Fold over list	`List.fold_left gcd 0`	`.iter().copied().reduce(gcd)`
Ownership cost	None (GC)	None (Copy types)
Overflow guard	Manual	`a / gcd(a, b) * b` pattern
Empty case	`0` or exception	`.unwrap_or(0)`

/// GCD using Euclidean algorithm
///
/// Ownership insight: All values are Copy (integers), so ownership
/// is trivial here. The recursive structure mirrors OCaml exactly.
pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 { a } else { gcd(b, a % b) }
}

/// LCM using GCD
pub fn lcm(a: u64, b: u64) -> u64 {
    if a == 0 || b == 0 { 0 } else { a / gcd(a, b) * b }
}

/// GCD of a slice — uses fold pattern like OCaml List.fold_left
/// Ownership: slice is borrowed, no allocation needed
pub fn gcd_list(nums: &[u64]) -> u64 {
    nums.iter().copied().reduce(gcd).unwrap_or(0)
}

/// Iterator-based GCD — more idiomatic Rust
pub fn gcd_iter(nums: impl IntoIterator<Item = u64>) -> u64 {
    nums.into_iter().reduce(gcd).unwrap_or(0)
}

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

    #[test]
    fn test_gcd_basic() {
        assert_eq!(gcd(48, 18), 6);
        assert_eq!(gcd(100, 75), 25);
    }

    #[test]
    fn test_gcd_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(0, 5), 0);
    }

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

    #[test]
    fn test_gcd_iter() {
        assert_eq!(gcd_iter(vec![48, 36, 60, 12]), 12);
    }
}

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

(* GCD and LCM — Euclidean Algorithm *)

(* Version 1: Basic recursive *)
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

(* Version 2: GCD over a list using fold *)
let gcd_list = function
  | [] -> 0
  | h :: t -> List.fold_left gcd h t

let () =
  assert (gcd 48 18 = 6);
  assert (lcm 12 18 = 36);
  assert (gcd_list [48; 36; 60; 12] = 12);
  Printf.printf "gcd(48,18) = %d\n" (gcd 48 18);
  Printf.printf "lcm(12,18) = %d\n" (lcm 12 18)

📊 Detailed Comparison

GCD and LCM — Comparison

Core Insight

The Euclidean algorithm is a pure recursive function on integers. Since integers are `Copy` in Rust, the translation is nearly identical — no ownership complications.

OCaml Approach

`let rec gcd a b = if b = 0 then a else gcd b (a mod b)` — concise one-liner
`List.fold_left gcd h t` — fold over list with GCD as combining function
Polymorphic integers (but typically `int`)

Rust Approach

Same recursive structure with explicit `u64` type
`iter().copied().reduce(gcd)` mirrors `fold_left`
Can also accept `impl IntoIterator` for generic input

Comparison Table

Aspect	OCaml	Rust
Recursion	`let rec`	plain `fn` (no keyword needed)
Modulo	`mod` (operator)	`%` (operator)
Fold	`List.fold_left`	`.iter().reduce()`
Integer type	`int` (63-bit)	`u64` (explicit)
Overflow	Silent wraparound	Panic in debug, wrap in release

Learner Notes

Rust requires explicit numeric types — no polymorphic `int`
`reduce` vs `fold`: reduce uses first element as initial value
For integers, ownership is trivial — everything is Copy
The `a / gcd(a,b) b` form avoids overflow vs `a b / gcd(a,b)`