Skip to content

Instantly share code, notes, and snippets.

@raeq
Created September 5, 2020 10:13
Show Gist options
  • Save raeq/9d6e8a11b0aacaf4a4d1dd1de4cc26cb to your computer and use it in GitHub Desktop.
Save raeq/9d6e8a11b0aacaf4a4d1dd1de4cc26cb to your computer and use it in GitHub Desktop.
Double matrix method for calculating Fibonacci
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