Skip to content

Instantly share code, notes, and snippets.

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

 #!/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+x,x),[(1,1)]*(n-2)) 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))
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.