Created
September 5, 2020 10:13
-
-
Save raeq/9d6e8a11b0aacaf4a4d1dd1de4cc26cb to your computer and use it in GitHub Desktop.
Double matrix method for calculating Fibonacci
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def matrix_fibonacci(target: int) -> int: | |
""" | |
This is the fastest way to compute a fibonacci number, using matrix mathematics. | |
It completes quickly. | |
The math is explained in detailed on the Wiki page at: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form | |
>>> matrix_fibonacci(80) | |
23416728348467685 | |
""" | |
v1, v2, v3 = ( | |
1, | |
1, | |
0, | |
) # initialise a matrix [[1,1],[1,0]] of the first two numbers in the sequence | |
for record in bin( | |
target | |
)[3:]: # perform fast exponentiation of the matrix (quickly raise it to the nth power) | |
calc = v2 * v2 | |
v1, v2 = v1 * v1 + calc, (v1 + v3) * v2 | |
v3 = calc + v3 * v3 | |
if record is "1": | |
v1, v2, v3 = v1 + v2, v1, v2 | |
return int(v2) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment