fibonacci - matrix exponentiation

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} $$

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]

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]

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]