Returns the nth number of the Fibonacci sequence that starts with f1 and f2 Uses the matrix exponentiation >>> fibonacci_with_matrix_exponentiation(1, 5, 6) 5 >>> fibonacci_with_matrix_exponentiation(2, 10, 11) 11 >>> fibonacci_with_matrix_exponentiation(13, 0, 1)
(n: int, f1: int, f2: int)
| 39 | |
| 40 | |
| 41 | def fibonacci_with_matrix_exponentiation(n: int, f1: int, f2: int) -> int: |
| 42 | """ |
| 43 | Returns the nth number of the Fibonacci sequence that |
| 44 | starts with f1 and f2 |
| 45 | Uses the matrix exponentiation |
| 46 | >>> fibonacci_with_matrix_exponentiation(1, 5, 6) |
| 47 | 5 |
| 48 | >>> fibonacci_with_matrix_exponentiation(2, 10, 11) |
| 49 | 11 |
| 50 | >>> fibonacci_with_matrix_exponentiation(13, 0, 1) |
| 51 | 144 |
| 52 | >>> fibonacci_with_matrix_exponentiation(10, 5, 9) |
| 53 | 411 |
| 54 | >>> fibonacci_with_matrix_exponentiation(9, 2, 3) |
| 55 | 89 |
| 56 | """ |
| 57 | # Trivial Cases |
| 58 | if n == 1: |
| 59 | return f1 |
| 60 | elif n == 2: |
| 61 | return f2 |
| 62 | matrix = Matrix([[1, 1], [1, 0]]) |
| 63 | matrix = modular_exponentiation(matrix, n - 2) |
| 64 | return f2 * matrix.t[0][0] + f1 * matrix.t[0][1] |
| 65 | |
| 66 | |
| 67 | def simple_fibonacci(n: int, f1: int, f2: int) -> int: |
nothing calls this directly
no test coverage detected