Crate fibo[−][src]
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 | 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). |