Skip to content

Instantly share code, notes, and snippets.

@chemacortes

chemacortes/fibo_matrix.py

Last active January 30, 2024 09:41
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save chemacortes/20e4529e19f2949ebd41c878882172df to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save chemacortes/20e4529e19f2949ebd41c878882172df to your computer and use it in GitHub Desktop.
Download ZIP
fibonacci - matrix exponentiation
Raw
readme.md

We can express python’s line

(cur, next) = (next, cur+next)

as a simple matrix multiplication :

$$ \begin{gather} X_0 = \begin{pmatrix} 0 & 1 \end{pmatrix} \\ X_n = M X_{n-1} \\ = M^n X_0 \end{gather} $$

Where

$$ M = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} $$

Raw
fibo_matrix.py
import numpy as np
import sys
sys.set_int_max_str_digits(0)
def matrix_power(A: np.matrix, n: int) -> np.matrix:
if n == 0:
return np.matrix( ((1,0),(0,1)), dtype=object )
elif n%2 == 1:
return np.matmul(A, matrix_power(A, n-1))
else:
root = matrix_power(A, n/2)
return np.matmul(root, root)
def fibo_matrix(n: int) -> int:
M = np.matrix( ((0, 1), (1,1)), dtype=object )
return matrix_power(M,n)[0,1]
Raw
fibo_matrix2.py
import numpy as np
import sys
sys.set_int_max_str_digits(0)
def matrix_power(A: np.matrix, n: int) -> np.matrix:
if n == 0:
return np.identity(2, dtype=object )
elif n%2 == 1:
return A @ matrix_power(A, n-1)
else:
root = matrix_power(A, n/2)
return root @ root
def fibo_matrix(n: int) -> int:
M = np.matrix( ((0, 1), (1,1)), dtype=object )
return matrix_power(M,n)[0,1]
Raw
fibo_matrix3.py
import numpy as np
import sys
sys.set_int_max_str_digits(0)
def fib(n: int) -> int:
M = np.matrix( ((0, 1), (1,1)), dtype=object )
return (M ** n)[0,1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment