Skip to content

Instantly share code, notes, and snippets.

@ivanyu
Last active January 18, 2023 20:33
Show Gist options
  • Save ivanyu/5768245 to your computer and use it in GitHub Desktop.
Save ivanyu/5768245 to your computer and use it in GitHub Desktop.
Fibonacci number in O( log N ) operations.
import time
import random
class MatrixFibonacci:
A = [[1, 1],
[1, 0]]
def __init__(self):
self.__memo = {}
def __multiply_matrices(self, M1, M2):
"""2x2 matrices multiplication"""
a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
r = [[a11, a12], [a21, a22]]
return r
def __get_matrix_power(self, M, p):
"""Calculate matrix power (p is a power of 2)"""
if p == 1:
return M
if p in self.__memo:
return self.__memo[p]
K = self.__get_matrix_power(M, int(p/2))
R = self.__multiply_matrices(K, K)
self.__memo[p] = R
return R
def get_number(self, n):
"""Get nth Fibonacci number (n is int, non-negative)."""
if n == 0:
return 0
if n == 1:
return 1
# Decompose to powers of 2,
# i.e. 62 = 2^5 + 2^4 + 2^3 + 2^2 + 2^0 = 32 + 16 + 8 + 4 + 1.
powers = [int(pow(2, b))
for (b, d) in enumerate(reversed(bin(n-1)[2:])) if d == '1']
# Less pythonic: http://pastebin.com/h8cKDkHX
matrices = [self.__get_matrix_power(MatrixFibonacci.A, p)
for p in powers]
while len(matrices) > 1:
M1 = matrices.pop()
M2 = matrices.pop()
R = self.__multiply_matrices(M1, M2)
matrices.append(R)
return matrices[0][0][0]
class IterationFibonacci:
def __init__(self):
pass
def get_number(self, n):
"""Get nth Fibonacci number (n is int, non-negative)."""
if n == 0:
return 0
a = 0
b = 1
c = 1
for i in range(n-1):
c = a + b
a = b
b = c
return c
def benchmark():
random.seed()
for around in range(10, 1010, 10):
ifib = IterationFibonacci()
mfib = MatrixFibonacci()
ti = 0
tm = 0
count = 10000
for _ in range(count):
n = random.randint(around-5, around+5)
t = time.time()
ifib.get_number(n)
t1 = time.time() - t
ti += t1
t = time.time()
mfib.get_number(n)
t2 = time.time() - t
tm += t2
print("{0}\t{1}\t{2}".format(around, ti, tm))
if __name__ == "__main__":
benchmark()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment