matrix.nth_fibonacci_using_matrix_exponentiation¶

Implementation of finding nth fibonacci number using matrix exponentiation. Time Complexity is about O(log(n)*8), where 8 is the complexity of matrix multiplication of size 2 by 2. And on the other hand complexity of bruteforce solution is O(n). As we know

f[n] = f[n-1] + f[n-1]

Converting to matrix,: [f(n),f(n-1)] = [[1,1],[1,0]] * [f(n-1),f(n-2)]
-> [f(n),f(n-1)] = [[1,1],[1,0]]^2 * [f(n-2),f(n-3)]

-> [f(n),f(n-1)] = [[1,1],[1,0]]^(n-1) * [f(1),f(0)] So we just need the n times multiplication of the matrix [1,1],[1,0]]. We can decrease the n times multiplication by following the divide and conquer approach.

Functions¶

`identity`(→ list[list[int]])
`main`(→ None)
`multiply`(→ list[list[int]])
`nth_fibonacci_bruteforce`(→ int)
`nth_fibonacci_matrix`(→ int)

Module Contents¶

matrix.nth_fibonacci_using_matrix_exponentiation.identity(n: int) → list[list[int]]¶

matrix.nth_fibonacci_using_matrix_exponentiation.main() → None¶

matrix.nth_fibonacci_using_matrix_exponentiation.multiply(matrix_a: list[list[int]], matrix_b: list[list[int]]) → list[list[int]]¶

matrix.nth_fibonacci_using_matrix_exponentiation.nth_fibonacci_bruteforce(n: int) → int¶

>>> nth_fibonacci_bruteforce(100)
354224848179261915075
>>> nth_fibonacci_bruteforce(-100)
-100

matrix.nth_fibonacci_using_matrix_exponentiation.nth_fibonacci_matrix(n: int) → int¶

>>> nth_fibonacci_matrix(100)
354224848179261915075
>>> nth_fibonacci_matrix(-100)
-100