fib.py

#!/usr/bin/env python
# Sasha Nikiforov

import numpy as np
import numpy.linalg as lg

from functools import reduce

# Not super optimal way to calculate N-th Fibonacci - taken
# from stackoverflow
fib=lambda n:reduce(lambda x,y:(x[0]+x[1],x[0]),[(1,1)]*(n-2))[0]

A = np.array((0, 1, 1,1)).reshape(2, 2)
# F-vector is first and second fibonacci number [1, 1]
F = np.array((1,1)).reshape(2, 1)

# eigenvalue factorization, V - vector of eigenvalues, S - orthogonal matrix
# of normilized eigenvectors
[V, S] = lg.eig(A)

# Just print out estimation of the matrix A - to see that it's pretty close
# to the original one 
A_hat = S.dot(np.diag(V)).dot(S.T)
print (str(A_hat))

N = 20

# Calculate N-th fibonacci 
print(fib(N))

# estimate N-th fibonacci, remember that we know 1 and 2 fibonacci, so V^2 will
# calculate 3rd fibonacci number
# S * V^(N - 3) * S^(T) * F
Fib_est = S.dot(np.diag(V**(N - 3))).dot(S.T).dot(F)
print(str(Fib_est[1]))