Crate fibo

Modules§

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).