Crate fibo

Modules

• mat

Traits

• Index

Functions

• fibo_mat
  Compute the n-th Fibonacci number modulo m using a Q-matrix with sequential matrix multiplication. The computation time is O(n).
• fibo_mat_loop
  Compute the n-th Fibonacci number modulo m using a Q-matrix with repeated squaring (using loops). Slightly faster than fibo_mat_req() since there are no function call overhead. The computation time is O(log(n)).
• fibo_mat_req
  Compute the n-th Fibonacci number modulo m using a Q-matrix with repeated squaring (using recurrsion). The computation time is O(log(n)).
• fibo_rec
  Compute the n-th Fibonacci number modulo m using recurssion (F(n) <= F(n-1) + F(n-2)). Since the recurrsion computes the same Fibonacci numbers multiple times, it is very slow to compute. The computation time is O(F(n)) = O(φ^n). Maybe n = ~40 is the maximum value that this function can compute the Fibonacci number.
• fibo_seq
  Compute the n-th Fibonacci number modulo m using sequencial computation ((F(n), F(n-1)) <= (F(n-1) + F(n-2), F(n-1))). The computation time is O(n).