31_fibonacci_matrix_power/
31_fibonacci_matrix_power.rs

1//! # Example: Fibonacci by Matrix Power
2//!
3//! Run: cargo run --example 31_fibonacci_matrix_power
4//!
5//! ## Problem
6//! Compute Fibonacci numbers using matrix multiplication instead of the usual
7//! additive recurrence.
8//!
9//! ## Math idea
10//! With `Q = [[1, 1], [1, 0]]`, raising `Q` to the n-th power gives
11//! ```text
12//! Q^n = [[F(n+1), F(n)],
13//!        [F(n),   F(n-1)]]
14//! ```
15//! so `F(n)` is the top-right entry of `Q^n` (with `F(0) = 0`, `F(1) = 1`).
16//!
17//! ## Tensor representation
18//! `Q` and the running product are 2×2 `Tensor`s. Each power step is a single
19//! `Tensor::matmul` call; the result entry is read with `Tensor::get(&[0, 1])`.
20//!
21//! ## What this demonstrates
22//! - 2×2 matrix construction;
23//! - repeated matrix multiplication via `Tensor::matmul` (note: `*` is
24//!   element-wise, never a matrix product);
25//! - reading a single matrix element with `Tensor::get`.
26//!
27//! ## Expected output
28//! ```text
29//! F(1..=10) via matrix power = 1 1 2 3 5 8 13 21 34 55
30//! Fibonacci by matrix power: OK
31//! ```
32//!
33//! Note: this is a demonstration of the matrix identity, not a big-integer
34//! Fibonacci routine — `f64` stays exact only for modest `n`.
35
36use matten::Tensor;
37
38/// `n`-th Fibonacci number via the matrix identity `Q^n`, with `F(0) = 0`.
39fn fib(n: u32) -> u64 {
40    let q = Tensor::new(vec![1.0, 1.0, 1.0, 0.0], &[2, 2]);
41    // Start from the 2×2 identity so that `fib(0)` returns 0.
42    let mut acc = Tensor::new(vec![1.0, 0.0, 0.0, 1.0], &[2, 2]);
43    for _ in 0..n {
44        acc = acc.matmul(&q);
45    }
46    // F(n) is the top-right entry of Q^n.
47    acc.get(&[0, 1]).expect("index in bounds") as u64
48}
49
50fn main() {
51    let expected = [1u64, 1, 2, 3, 5, 8, 13, 21, 34, 55];
52
53    print!("F(1..=10) via matrix power =");
54    for n in 1..=10u32 {
55        let f = fib(n);
56        print!(" {f}");
57        assert_eq!(f, expected[(n - 1) as usize]);
58    }
59    println!();
60
61    assert_eq!(fib(0), 0);
62    println!("Fibonacci by matrix power: OK");
63}
31_fibonacci_matrix_power/31_fibonacci_matrix_power.rs

31_fibonacci_matrix_power/
31_fibonacci_matrix_power.rs
