087 Fundamental

087 — Difference of Squares

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "087 — Difference of Squares" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Compute the difference between the square of the sum and the sum of the squares of the first `n` natural numbers. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Compute the difference between the square of the sum and the sum of the squares of the first n natural numbers. Implement both an iterator-based O(n) version and a closed-form O(1) version using the formulas (n(n+1)/2)² and n(n+1)(2n+1)/6. Compare with OCaml's List.init and List.fold_left approach.

🎯 Learning Outcomes

• Use (1..=n).sum() for range summation and .map(|x| x * x).sum() for sum of squares

• Understand Rust's ..= inclusive range syntax

• Compare iterator-based O(n) computation with O(1) closed-form formulas

• Use the Gauss formula n(n+1)/2 and squares formula n(n+1)(2n+1)/6

• Map Rust's (1..=n) range to OCaml's List.init n (fun i -> i + 1)

• Verify both implementations agree with property-based reasoning

Code Example

#![allow(clippy::all)]
/// Difference of Squares
///
/// Ownership: All values are Copy integers. No ownership concerns.

/// Square of the sum of first n natural numbers
pub fn square_of_sum(n: u64) -> u64 {
    let s: u64 = (1..=n).sum();
    s * s
}

/// Sum of the squares of first n natural numbers
pub fn sum_of_squares(n: u64) -> u64 {
    (1..=n).map(|x| x * x).sum()
}

/// Difference
pub fn difference(n: u64) -> u64 {
    square_of_sum(n) - sum_of_squares(n)
}

/// Version 2: Using closed-form formulas (O(1))
pub fn square_of_sum_formula(n: u64) -> u64 {
    let s = n * (n + 1) / 2;
    s * s
}

pub fn sum_of_squares_formula(n: u64) -> u64 {
    n * (n + 1) * (2 * n + 1) / 6
}

pub fn difference_formula(n: u64) -> u64 {
    square_of_sum_formula(n) - sum_of_squares_formula(n)
}

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

    #[test]
    fn test_square_of_sum() {
        assert_eq!(square_of_sum(10), 3025);
    }

    #[test]
    fn test_sum_of_squares() {
        assert_eq!(sum_of_squares(10), 385);
    }

    #[test]
    fn test_difference() {
        assert_eq!(difference(10), 2640);
    }

    #[test]
    fn test_one() {
        assert_eq!(difference(1), 0);
    }

    #[test]
    fn test_formula_matches() {
        for n in 1..=100 {
            assert_eq!(difference(n), difference_formula(n));
        }
    }

    #[test]
    fn test_large() {
        assert_eq!(difference_formula(100), 25164150);
    }
}

(* Difference of Squares *)

(* Version 1: Using fold *)
let square_of_sum n =
  let s = List.init n (fun i -> i + 1) |> List.fold_left (+) 0 in
  s * s

let sum_of_squares n =
  List.init n (fun i -> i + 1)
  |> List.fold_left (fun acc x -> acc + x * x) 0

let difference n = square_of_sum n - sum_of_squares n

(* Version 2: Closed-form *)
let square_of_sum_formula n =
  let s = n * (n + 1) / 2 in s * s

let sum_of_squares_formula n =
  n * (n + 1) * (2 * n + 1) / 6

let () =
  assert (difference 10 = 2640);
  assert (square_of_sum_formula 10 = square_of_sum 10);
  assert (sum_of_squares_formula 10 = sum_of_squares 10)

Key Differences

Aspect	Rust	OCaml
Range	`(1..=n)`	`List.init n (fun i -> i+1)`
Sum	`.sum()`	`List.fold_left (+) 0`
Sum of squares	`.map(\|x\| x*x).sum()`	`List.fold_left (fun acc x -> acc + x*x) 0`
Closed form	Arithmetic on `u64`	Same arithmetic
Overflow	Possible for large `n` with `u64`	Same
Laziness	Iterator chain is lazy	`List.init` is eager (allocates list)

The two implementations illustrate a key lesson: recognise when a loop can be replaced by a closed-form expression. For this problem the O(1) formula is strictly better; the iterator version is shown to demonstrate the connection between the mathematical definition and the code.

OCaml Approach

List.init n (fun i -> i + 1) creates [1; 2; …; n]. List.fold_left (+) 0 sums it. List.fold_left (fun acc x -> acc + x * x) 0 sums squares. The closed-form formulas are identical arithmetic. OCaml's List.init is slightly more verbose than Rust's range iterator but maps naturally to the mathematical definition.

Full Source

#![allow(clippy::all)]
/// Difference of Squares
///
/// Ownership: All values are Copy integers. No ownership concerns.

/// Square of the sum of first n natural numbers
pub fn square_of_sum(n: u64) -> u64 {
    let s: u64 = (1..=n).sum();
    s * s
}

/// Sum of the squares of first n natural numbers
pub fn sum_of_squares(n: u64) -> u64 {
    (1..=n).map(|x| x * x).sum()
}

/// Difference
pub fn difference(n: u64) -> u64 {
    square_of_sum(n) - sum_of_squares(n)
}

/// Version 2: Using closed-form formulas (O(1))
pub fn square_of_sum_formula(n: u64) -> u64 {
    let s = n * (n + 1) / 2;
    s * s
}

pub fn sum_of_squares_formula(n: u64) -> u64 {
    n * (n + 1) * (2 * n + 1) / 6
}

pub fn difference_formula(n: u64) -> u64 {
    square_of_sum_formula(n) - sum_of_squares_formula(n)
}

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

    #[test]
    fn test_square_of_sum() {
        assert_eq!(square_of_sum(10), 3025);
    }

    #[test]
    fn test_sum_of_squares() {
        assert_eq!(sum_of_squares(10), 385);
    }

    #[test]
    fn test_difference() {
        assert_eq!(difference(10), 2640);
    }

    #[test]
    fn test_one() {
        assert_eq!(difference(1), 0);
    }

    #[test]
    fn test_formula_matches() {
        for n in 1..=100 {
            assert_eq!(difference(n), difference_formula(n));
        }
    }

    #[test]
    fn test_large() {
        assert_eq!(difference_formula(100), 25164150);
    }
}

(* Difference of Squares *)

(* Version 1: Using fold *)
let square_of_sum n =
  let s = List.init n (fun i -> i + 1) |> List.fold_left (+) 0 in
  s * s

let sum_of_squares n =
  List.init n (fun i -> i + 1)
  |> List.fold_left (fun acc x -> acc + x * x) 0

let difference n = square_of_sum n - sum_of_squares n

(* Version 2: Closed-form *)
let square_of_sum_formula n =
  let s = n * (n + 1) / 2 in s * s

let sum_of_squares_formula n =
  n * (n + 1) * (2 * n + 1) / 6

let () =
  assert (difference 10 = 2640);
  assert (square_of_sum_formula 10 = square_of_sum 10);
  assert (sum_of_squares_formula 10 = sum_of_squares 10)

✓ Tests Rust test suite

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

    #[test]
    fn test_square_of_sum() {
        assert_eq!(square_of_sum(10), 3025);
    }

    #[test]
    fn test_sum_of_squares() {
        assert_eq!(sum_of_squares(10), 385);
    }

    #[test]
    fn test_difference() {
        assert_eq!(difference(10), 2640);
    }

    #[test]
    fn test_one() {
        assert_eq!(difference(1), 0);
    }

    #[test]
    fn test_formula_matches() {
        for n in 1..=100 {
            assert_eq!(difference(n), difference_formula(n));
        }
    }

    #[test]
    fn test_large() {
        assert_eq!(difference_formula(100), 25164150);
    }
}

Deep Comparison

Difference of Squares — Comparison

Core Insight

Simple mathematical computations highlight the difference between OCaml's list-based iteration and Rust's range iterators. Rust ranges are lazy and allocation-free; OCaml's List.init creates a temporary list.

OCaml Approach

• List.init n (fun i -> i + 1) creates [1..n] as a list (heap allocation)

• List.fold_left (+) 0 sums the list

• |> pipe operator chains transformations

• Closed-form formulas avoid list creation

Rust Approach

• (1..=n) creates a lazy range (no allocation)

• .sum() and .map(|x| x * x).sum() consume the iterator

• Ranges are zero-cost abstractions

• Same closed-form formulas work identically

Comparison Table

Aspect	OCaml	Rust
Range	`List.init n (fun i -> i+1)`	`(1..=n)`
Sum	`List.fold_left (+) 0`	`.sum()`
Map+Sum	`fold_left (fun acc x -> ...)`	`.map().sum()`
Allocation	List created in memory	Zero allocation (lazy)
Overflow	Silent	Panic in debug mode

Learner Notes

• Rust ranges 1..=n are inclusive; 1..n is exclusive (like Python)

• .sum() requires type annotation sometimes: let s: u64 = (1..=n).sum()

• OCaml List.init is O(n) space; Rust ranges are O(1) space

• Both closed-form versions are O(1) time and space

Exercises

Prove algebraically that (n(n+1)/2)² - n(n+1)(2n+1)/6 simplifies to n(n-1)(n+1)(3n+2)/12.

Use u128 instead of u64 to handle larger inputs without overflow.

Write a property-based test that verifies difference_formula(n) == difference(n) for n in 1..=100.

Generalise to difference_k(n, k): square of the sum of kth powers minus sum of kth-power squares.

In OCaml, implement the closed-form version and measure execution time for n = 10_000_000 against the List.init version.

Open Source Repos

functional-rust

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

Rust