076 Intermediate

076 — GCD and LCM (Ownership Focus)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "076 — GCD and LCM (Ownership Focus)" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. This example revisits GCD and LCM (see also example 071) with an explicit focus on ownership semantics. Key difference from OCaml: 1. **`Copy` eliminates ownership friction**: With `Copy` types, Rust code looks identical to OCaml code for pure numeric algorithms. Ownership only matters for heap

Tutorial

The Problem

This example revisits GCD and LCM (see also example 071) with an explicit focus on ownership semantics. Since GCD operates on u64 (a Copy type), ownership is trivial — values are copied freely. This makes GCD a clean example for understanding when Rust's ownership system has zero friction: primitive types are Copy, so they move like values in any other language.

The ownership-focused presentation shows that Rust's borrow checker is not an obstacle for numeric code — Copy types eliminate the entire class of ownership errors that arise with heap-allocated types.

🎯 Learning Outcomes

• Understand why ownership is trivial for Copy types (integers)

• Use reduce to apply a binary operation across a collection

• Implement gcd_iter accepting impl IntoIterator for maximum flexibility

• Recognize that gcd and lcm are commutative, associative operations suitable for reduce

• Connect to number theory: GCD as the basis for fraction simplification and coprimeness

Code Example

#![allow(clippy::all)]
/// 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);
    }
}

(* 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)

Key Differences

**Copy eliminates ownership friction**: With Copy types, Rust code looks identical to OCaml code for pure numeric algorithms. Ownership only matters for heap-allocated types.

**reduce vs fold**: Rust's reduce uses the first element as the initial accumulator. OCaml's fold_left gcd 0 uses 0 (the identity for GCD). Both compute the GCD of the collection.

**IntoIterator generality**: Rust's gcd_iter(impl IntoIterator<Item=u64>) works with slices, Vec, ranges, and custom iterators. OCaml's List.fold_left gcd 0 works only with lists.

Overflow prevention: a / gcd * b vs a * b / gcd — the first form avoids intermediate overflow. Both give the same mathematical result for valid inputs.

OCaml Approach

OCaml's Euclidean GCD is a direct tail-recursive function:

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

(* GCD of a list using fold — gcd(0, x) = x as identity *)
let gcd_list lst = List.fold_left gcd 0 lst

(* LCM of a list — lcm(1, x) = x as identity *)
let lcm_list lst = List.fold_left lcm 1 lst

All integers in OCaml are value types (like Rust's Copy types), so there are no ownership issues. The standard library added Int.gcd in OCaml 4.14.

Full Source

#![allow(clippy::all)]
/// 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);
    }
}

(* 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)

✓ Tests Rust test suite

#[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);
    }
}

Deep 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)

Exercises

Coprime check: Write are_coprime(a: u64, b: u64) -> bool using GCD. Prove that gcd(a, b) = 1 iff a and b are coprime. Use this for RSA key validation.

Totient function: Write totient(n: u64) -> u64 (Euler's totient function) counting integers from 1 to n that are coprime to n. Use (1..=n).filter(|&k| are_coprime(k, n)).count().

Farey sequence: Generate the Farey sequence F_n: all fractions p/q with 0 ≤ p ≤ q ≤ n and gcd(p,q) = 1, in ascending order. Use GCD to filter to reduced fractions.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust