Skip to content

Instantly share code, notes, and snippets.

@venik venik/fib.py
Last active Oct 17, 2017

Embed
What would you like to do?
#!/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]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.