827 Intermediate

Modular Arithmetic

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Modular Arithmetic" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. When computing large combinatorial values (n! Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

When computing large combinatorial values (n! mod p, binomial coefficients, number of paths), intermediate results overflow 64-bit integers long before the final answer. Modular arithmetic performs all operations in a finite field Z/pZ, keeping values bounded. Computing (a + b) % m, (a * b) % m, pow(a, b, m), and inv(a, m) are the building blocks of competitive programming, cryptography, and number theory. The key insight: (a * b) % m = ((a % m) * (b % m)) % m. Modular exponentiation (fast power) runs in O(log b) and is essential for RSA, Diffie-Hellman, and primality testing.

🎯 Learning Outcomes

• Implement modular addition, subtraction, and multiplication with proper overflow prevention

• Implement fast modular exponentiation via repeated squaring in O(log exp) time

• Understand modular inverse and when it exists (only when gcd(a, m) = 1)

• Compute factorial and binomial coefficients modulo a prime efficiently

• Recognize when to use Fermat's little theorem vs. extended Euclidean for modular inverse

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Modular Arithmetic in OCaml *)

(* Modular addition *)
let mod_add a b m = (a + b) mod m

(* Modular subtraction — ensure non-negative *)
let mod_sub a b m = ((a - b) mod m + m) mod m

(* Modular multiplication — use Int64 to avoid overflow for large values *)
let mod_mul a b m =
  Int64.(to_int (rem (mul (of_int a) (of_int b)) (of_int m)))

(* Fast modular exponentiation: a^exp mod m *)
let rec pow_mod (a : int) (exp : int) (m : int) : int =
  if exp = 0 then 1
  else if exp mod 2 = 0 then
    let half = pow_mod a (exp / 2) m in
    mod_mul half half m
  else
    mod_mul a (pow_mod a (exp - 1) m) m

(* Modular inverse via Fermat's little theorem (m must be prime) *)
let mod_inv_fermat (a : int) (p : int) : int =
  pow_mod a (p - 2) p

(* Extended Euclidean Algorithm: returns (gcd, x, y) s.t. ax + by = gcd *)
let rec extended_gcd (a : int) (b : int) : int * int * int =
  if b = 0 then (a, 1, 0)
  else
    let (g, x, y) = extended_gcd b (a mod b) in
    (g, y, x - (a / b) * y)

(* Modular inverse via Extended Euclidean (works for any coprime a, m) *)
let mod_inv (a : int) (m : int) : int option =
  let (g, x, _) = extended_gcd (((a mod m) + m) mod m) m in
  if g <> 1 then None
  else Some (((x mod m) + m) mod m)

let () =
  let m = 1_000_000_007 in
  Printf.printf "mod_add(999_999_999, 9, %d) = %d\n" m (mod_add 999_999_999 9 m);
  Printf.printf "mod_sub(3, 7, 10) = %d  (expected 6)\n" (mod_sub 3 7 10);
  Printf.printf "mod_mul(123456, 789012, %d) = %d\n" m (mod_mul 123456 789012 m);
  Printf.printf "pow_mod(2, 10, %d) = %d  (expected 1024)\n" m (pow_mod 2 10 m);
  Printf.printf "mod_inv_fermat(3, 7) = %d  (expected 5, since 3*5=15≡1 mod 7)\n"
    (mod_inv_fermat 3 7);
  (match mod_inv 3 7 with
   | Some inv -> Printf.printf "mod_inv(3, 7) = %d\n" inv
   | None -> Printf.printf "mod_inv(3, 7): no inverse\n");
  (* Verify: 3 * inv ≡ 1 mod 7 *)
  let inv = Option.get (mod_inv 3 7) in
  Printf.printf "3 * %d mod 7 = %d  (should be 1)\n" inv (mod_mul 3 inv 7)

Key Differences

Aspect	Rust	OCaml
Overflow risk	`u64 * u64` overflows above 2^32 mod	`int * int` overflows above 2^30 mod
Large modulus	Use `u128` intermediate	Use `Int64` or `Zarith`
Mod exponentiation	Iterative with bit manipulation	Recursive or iterative
Modular inverse	`mod_pow(a, m-2, m)` for prime m	Same via Fermat
Binomial coefficients	Precompute factorial array mod p	Same approach
Newtype safety	`struct Mod<const M: u64>(u64)`	`type modint = int` (no enforcement)

OCaml Approach

OCaml's int is 63-bit on 64-bit systems, allowing products up to about 4.6 * 10^18. For moduli up to 2^30, a * b mod m stays in bounds. For larger moduli, OCaml uses Int64 or Zarith. Modular exponentiation is a clean tail-recursive function: let rec pow_mod base exp m = if exp = 0 then 1 else let half = pow_mod (base * base mod m) (exp / 2) m in if exp mod 2 = 0 then half else half * base mod m. OCaml's Fun.protect ensures cleanup in modular operations with side effects.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Modular Arithmetic in OCaml *)

(* Modular addition *)
let mod_add a b m = (a + b) mod m

(* Modular subtraction — ensure non-negative *)
let mod_sub a b m = ((a - b) mod m + m) mod m

(* Modular multiplication — use Int64 to avoid overflow for large values *)
let mod_mul a b m =
  Int64.(to_int (rem (mul (of_int a) (of_int b)) (of_int m)))

(* Fast modular exponentiation: a^exp mod m *)
let rec pow_mod (a : int) (exp : int) (m : int) : int =
  if exp = 0 then 1
  else if exp mod 2 = 0 then
    let half = pow_mod a (exp / 2) m in
    mod_mul half half m
  else
    mod_mul a (pow_mod a (exp - 1) m) m

(* Modular inverse via Fermat's little theorem (m must be prime) *)
let mod_inv_fermat (a : int) (p : int) : int =
  pow_mod a (p - 2) p

(* Extended Euclidean Algorithm: returns (gcd, x, y) s.t. ax + by = gcd *)
let rec extended_gcd (a : int) (b : int) : int * int * int =
  if b = 0 then (a, 1, 0)
  else
    let (g, x, y) = extended_gcd b (a mod b) in
    (g, y, x - (a / b) * y)

(* Modular inverse via Extended Euclidean (works for any coprime a, m) *)
let mod_inv (a : int) (m : int) : int option =
  let (g, x, _) = extended_gcd (((a mod m) + m) mod m) m in
  if g <> 1 then None
  else Some (((x mod m) + m) mod m)

let () =
  let m = 1_000_000_007 in
  Printf.printf "mod_add(999_999_999, 9, %d) = %d\n" m (mod_add 999_999_999 9 m);
  Printf.printf "mod_sub(3, 7, 10) = %d  (expected 6)\n" (mod_sub 3 7 10);
  Printf.printf "mod_mul(123456, 789012, %d) = %d\n" m (mod_mul 123456 789012 m);
  Printf.printf "pow_mod(2, 10, %d) = %d  (expected 1024)\n" m (pow_mod 2 10 m);
  Printf.printf "mod_inv_fermat(3, 7) = %d  (expected 5, since 3*5=15≡1 mod 7)\n"
    (mod_inv_fermat 3 7);
  (match mod_inv 3 7 with
   | Some inv -> Printf.printf "mod_inv(3, 7) = %d\n" inv
   | None -> Printf.printf "mod_inv(3, 7): no inverse\n");
  (* Verify: 3 * inv ≡ 1 mod 7 *)
  let inv = Option.get (mod_inv 3 7) in
  Printf.printf "3 * %d mod 7 = %d  (should be 1)\n" inv (mod_mul 3 inv 7)

Deep Comparison

OCaml vs Rust: Modular Arithmetic

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement a ModInt<const M: u64> newtype that overloads arithmetic operators to auto-apply modular reduction.

Precompute factorial and inverse factorial tables mod p to answer n-choose-k queries in O(1).

Implement Lucas' theorem for computing binomial coefficients mod a prime p for very large n, k.

Use modular arithmetic to verify matrix multiplication: (A * B) % m = ((A % m) * (B % m)) % m.

Benchmark u64 vs. u128 intermediate for modular multiplication and measure the throughput difference.

Open Source Repos

functional-rust

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

Rust