778 Intermediate

778-const-fibonacci — Const Fibonacci

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "778-const-fibonacci — Const Fibonacci" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Fibonacci numbers appear in algorithm analysis, financial modeling, and data structure design (Fibonacci heaps). Key difference from OCaml: 1. **True compile time**: Rust's `const fn fib(n)` evaluates during `rustc` compilation; OCaml's equivalent runs at program startup.

Tutorial

The Problem

Fibonacci numbers appear in algorithm analysis, financial modeling, and data structure design (Fibonacci heaps). Computing them at compile time eliminates startup overhead for lookup tables and serves as a benchmark for const fn capability. This example implements three approaches — naive recursion, iterative, and matrix exponentiation — and compares their feasibility and efficiency in const contexts, demonstrating how const fn restrictions shape algorithm choices.

🎯 Learning Outcomes

• Implement const fn fib_recursive(n: u64) — exponential but simple, limited by recursion depth limits

• Implement const fn fib_iterative(n: u64) using while loops — O(n), works for large n

• Implement const fn fib_matrix(n: u64) using matrix exponentiation — O(log n) in const context

• Compute const FIB_30: u64 = fib_iterative(30) to verify compile-time evaluation

• Understand why recursive const functions hit depth limits for large inputs

Code Example

pub const fn fib_iterative(n: u64) -> u64 {
    let mut a = 0u64;
    let mut b = 1u64;
    let mut i = 1;
    while i < n {
        let temp = a + b;
        a = b;
        b = temp;
        i += 1;
    }
    b
}

// Computed at compile time!
pub const FIB_20: u64 = fib_iterative(20);

(* Computed at module initialization *)
let fib_iterative n =
  let rec loop a b i =
    if i >= n then b
    else loop b (a + b) (i + 1)
  in
  if n = 0 then 0 else loop 0 1 1

let fib_20 = fib_iterative 20

Key Differences

True compile time: Rust's const fn fib(n) evaluates during rustc compilation; OCaml's equivalent runs at program startup.

Recursion depth: Rust limits const fn recursion depth (configurable via -Zunleash-the-miri-inside-of-you); OCaml's startup-time evaluation has no such limit.

Loop support: Rust's while loop in const fn (since Rust 1.46) enables efficient iterative algorithms; OCaml has no equivalent.

Build scripts: Both languages can generate lookup tables via build scripts (build.rs in Rust, Dune rules in OCaml), avoiding language-level const computation.

OCaml Approach

OCaml cannot compute Fibonacci at compile time directly. Module-level let bindings are evaluated at program startup, not during compilation. A common approach is code generation: a script generates let fib_table = [| 0; 1; 1; 2; 3; 5; ... |] as a source file. For small n, the [@@unrolled] attribute can help the compiler specialize, but this is not true compile-time computation.

Full Source

#![allow(clippy::all)]
//! # Const Fibonacci
//!
//! Computing Fibonacci numbers at compile time.

/// Naive recursive Fibonacci (works for small n in const)
pub const fn fib_recursive(n: u64) -> u64 {
    match n {
        0 => 0,
        1 => 1,
        _ => fib_recursive(n - 1) + fib_recursive(n - 2),
    }
}

/// Iterative Fibonacci (efficient for const)
pub const fn fib_iterative(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    let mut a = 0u64;
    let mut b = 1u64;
    let mut i = 1;
    while i < n {
        let temp = a + b;
        a = b;
        b = temp;
        i += 1;
    }
    b
}

/// Matrix exponentiation Fibonacci (O(log n) at compile time)
pub const fn fib_matrix(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }

    // Matrix [[1,1],[1,0]]^n
    let (mut a, mut b, mut c, mut d) = (1u64, 1u64, 1u64, 0u64);
    let (mut ra, mut rb, mut rc, mut rd) = (1u64, 0u64, 0u64, 1u64); // Identity

    let mut exp = n - 1;
    while exp > 0 {
        if exp % 2 == 1 {
            let new_ra = ra * a + rb * c;
            let new_rb = ra * b + rb * d;
            let new_rc = rc * a + rd * c;
            let new_rd = rc * b + rd * d;
            ra = new_ra;
            rb = new_rb;
            rc = new_rc;
            rd = new_rd;
        }
        let new_a = a * a + b * c;
        let new_b = a * b + b * d;
        let new_c = c * a + d * c;
        let new_d = c * b + d * d;
        a = new_a;
        b = new_b;
        c = new_c;
        d = new_d;
        exp /= 2;
    }

    ra
}

/// Check if n is a Fibonacci number
pub const fn is_fibonacci(n: u64) -> bool {
    if n == 0 {
        return true;
    }
    let mut a = 0u64;
    let mut b = 1u64;
    while b < n {
        let temp = a + b;
        a = b;
        b = temp;
    }
    b == n
}

/// Generate Fibonacci array at compile time
pub const fn fib_array<const N: usize>() -> [u64; N] {
    let mut arr = [0u64; N];
    if N > 0 {
        arr[0] = 0;
    }
    if N > 1 {
        arr[1] = 1;
    }
    let mut i = 2;
    while i < N {
        arr[i] = arr[i - 1] + arr[i - 2];
        i += 1;
    }
    arr
}

// Compile-time constants
pub const FIB_10: u64 = fib_iterative(10);
pub const FIB_20: u64 = fib_iterative(20);
pub const FIB_FIRST_20: [u64; 20] = fib_array();

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

    #[test]
    fn test_fib_recursive() {
        assert_eq!(fib_recursive(0), 0);
        assert_eq!(fib_recursive(1), 1);
        assert_eq!(fib_recursive(10), 55);
    }

    #[test]
    fn test_fib_iterative() {
        assert_eq!(fib_iterative(0), 0);
        assert_eq!(fib_iterative(1), 1);
        assert_eq!(fib_iterative(10), 55);
        assert_eq!(fib_iterative(20), 6765);
    }

    #[test]
    fn test_fib_matrix() {
        assert_eq!(fib_matrix(0), 0);
        assert_eq!(fib_matrix(1), 1);
        assert_eq!(fib_matrix(10), 55);
        assert_eq!(fib_matrix(20), 6765);
    }

    #[test]
    fn test_is_fibonacci() {
        assert!(is_fibonacci(0));
        assert!(is_fibonacci(1));
        assert!(is_fibonacci(55));
        assert!(is_fibonacci(6765));
        assert!(!is_fibonacci(4));
        assert!(!is_fibonacci(100));
    }

    #[test]
    fn test_fib_array() {
        assert_eq!(FIB_FIRST_20[10], 55);
        assert_eq!(FIB_FIRST_20[19], 4181);
    }

    #[test]
    fn test_compile_time_values() {
        assert_eq!(FIB_10, 55);
        assert_eq!(FIB_20, 6765);
    }

    // Compile-time verification
    const _: () = assert!(fib_iterative(10) == 55);
    const _: () = assert!(fib_matrix(10) == fib_iterative(10));
}

(* Fibonacci at 'compile time' (load time) in OCaml *)

(* Elegant recursive definition *)
let rec fib_rec n =
  if n <= 1 then n
  else fib_rec (n-1) + fib_rec (n-2)

(* Memoized version (Hashtbl) *)
let memo = Hashtbl.create 100

let rec fib_memo n =
  if n <= 1 then n
  else match Hashtbl.find_opt memo n with
  | Some v -> v
  | None ->
    let v = fib_memo (n-1) + fib_memo (n-2) in
    Hashtbl.replace memo n v;
    v

(* Table (computed once at module load — analogous to const in Rust) *)
let fib_table =
  let t = Array.make 93 0 in
  t.(0) <- 0; t.(1) <- 1;
  for i = 2 to 92 do
    t.(i) <- t.(i-1) + t.(i-2)
  done;
  t

let fib n = fib_table.(n)

let () =
  Printf.printf "Recursive  fib(10) = %d\n" (fib_rec 10);
  Printf.printf "Memoized   fib(40) = %d\n" (fib_memo 40);
  Printf.printf "Table      fib(50) = %d\n" (fib 50);
  Printf.printf "fib(1..10) = ";
  for i = 0 to 10 do
    Printf.printf "%d " (fib i)
  done;
  print_newline ()

✓ Tests Rust test suite

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

    #[test]
    fn test_fib_recursive() {
        assert_eq!(fib_recursive(0), 0);
        assert_eq!(fib_recursive(1), 1);
        assert_eq!(fib_recursive(10), 55);
    }

    #[test]
    fn test_fib_iterative() {
        assert_eq!(fib_iterative(0), 0);
        assert_eq!(fib_iterative(1), 1);
        assert_eq!(fib_iterative(10), 55);
        assert_eq!(fib_iterative(20), 6765);
    }

    #[test]
    fn test_fib_matrix() {
        assert_eq!(fib_matrix(0), 0);
        assert_eq!(fib_matrix(1), 1);
        assert_eq!(fib_matrix(10), 55);
        assert_eq!(fib_matrix(20), 6765);
    }

    #[test]
    fn test_is_fibonacci() {
        assert!(is_fibonacci(0));
        assert!(is_fibonacci(1));
        assert!(is_fibonacci(55));
        assert!(is_fibonacci(6765));
        assert!(!is_fibonacci(4));
        assert!(!is_fibonacci(100));
    }

    #[test]
    fn test_fib_array() {
        assert_eq!(FIB_FIRST_20[10], 55);
        assert_eq!(FIB_FIRST_20[19], 4181);
    }

    #[test]
    fn test_compile_time_values() {
        assert_eq!(FIB_10, 55);
        assert_eq!(FIB_20, 6765);
    }

    // Compile-time verification
    const _: () = assert!(fib_iterative(10) == 55);
    const _: () = assert!(fib_matrix(10) == fib_iterative(10));
}

Deep Comparison

OCaml vs Rust: Const Fibonacci

Compile-Time Computation

Rust

pub const fn fib_iterative(n: u64) -> u64 {
    let mut a = 0u64;
    let mut b = 1u64;
    let mut i = 1;
    while i < n {
        let temp = a + b;
        a = b;
        b = temp;
        i += 1;
    }
    b
}

// Computed at compile time!
pub const FIB_20: u64 = fib_iterative(20);

OCaml

(* Computed at module initialization *)
let fib_iterative n =
  let rec loop a b i =
    if i >= n then b
    else loop b (a + b) (i + 1)
  in
  if n = 0 then 0 else loop 0 1 1

let fib_20 = fib_iterative 20

Compile-Time Arrays

Rust

pub const fn fib_array<const N: usize>() -> [u64; N] {
    let mut arr = [0u64; N];
    // ... fill at compile time
    arr
}

pub const FIB_FIRST_20: [u64; 20] = fib_array();

OCaml

(* Runtime array creation *)
let fib_first_20 = Array.init 20 fib_iterative

Key Differences

Aspect	OCaml	Rust
Evaluation time	Module init	Compile time
Binary size	Code + runtime	Embedded values
Startup cost	Computation	None
Verification	Runtime tests	`const { assert!() }`

Exercises

Use const fn fib_iterative to generate a complete Fibonacci lookup table: const FIB_TABLE: [u64; 93] = generate_fib_table().

Implement const fn fib_last_digit(n: u64) -> u8 that computes fib(n) % 10 without overflow, using the Pisano period property that the last digit repeats with period 60.

Write a const fn golden_ratio_approx(n: u32) -> (u64, u64) that returns (fib(n+1), fib(n)) as a rational approximation of the golden ratio.

Open Source Repos

functional-rust

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

Rust