940 Gcd Lcm
Functional Programming
Tutorial
The Problem
Implement GCD (greatest common divisor) and LCM (least common multiple) using Euclid's algorithm. Extend the scalar operations to lists using fold/reduce, and compare a recursive implementation against an iterative one. Both algorithms are elegant in functional style and highlight Rust's tail-call behavior relative to OCaml's TCO guarantee.
🎯 Learning Outcomes
gcd(a, b) = gcd(b, a % b) with base case b == 0lcm(a, b) = a / gcd(a, b) * b (divide before multiplying to avoid overflow)Iterator::reduceCode Example
#![allow(clippy::all)]
/// # 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));
}
}Key Differences
| Aspect | Rust | OCaml |
|---|---|---|
| Tail-call optimization | Not guaranteed; use iterative for safety | Guaranteed for tail-recursive functions |
reduce vs fold_left | reduce uses first element as init; fold_left needs explicit identity | fold_left — same semantics |
| Integer overflow | u64 saturates silently at limits; divide-first avoids overflow | Same; Int64 or arbitrary precision for big numbers |
| Pattern match style | if b == 0 { a } else { ... } | if b = 0 then a else ... |
The recursive implementation reads almost identically in both languages. The practical difference is that OCaml's TCO guarantee means you can safely use recursion for arbitrarily large inputs, while Rust's iterative version is the production-safe choice for unknown input sizes.
OCaml Approach
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 a / gcd a b * b
let gcd_list = List.fold_left gcd 0
let lcm_list = List.fold_left lcm 1
(* Tail position: OCaml guarantees TCO here *)
(* gcd is already in tail position — the recursive call is the last action *)
OCaml guarantees tail-call optimization for functions in tail position. The recursive gcd above calls gcd b (a mod b) as its final action — this is a proper tail call, so OCaml compiles it to a loop. No stack frames accumulate regardless of input size.
Full Source
#![allow(clippy::all)]
/// # 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));
}
}
✓ Tests
Rust test suite
#[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));
}
}Deep 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
reduce() vs fold()** — reduce uses the first element as init, returns Option; fold takes explicit inita / gcd(a,b) * b avoids the a * b overflow that lcm could hitu64 means no negatives** — simpler than OCaml's signed int, but requires type choice upfront.copied()** — converts &u64 to u64 in the iterator chain (like OCaml's implicit value semantics)Further Reading
Exercises
gcd(a, 0) = a, gcd(0, a) = a, gcd(a, b) = gcd(b, a).coprime(a, b) -> bool using GCD and use it to filter pairs from a list.lcm(1..=20) — the smallest number divisible by 1 through 20 (Project Euler problem 5).i64 with proper sign handling (gcd(|a|, |b|)).