Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import time
- import numpy as np
- from concurrent.futures import ThreadPoolExecutor
- def FIB(N):
- if N <= 1:
- return N
- else:
- return FIB(N - 1) + FIB(N - 2)
- def MEASURE_TIME_FIB(N):
- START_TIME = time.time()
- RESULT = FIB(N)
- END_TIME = time.time()
- return RESULT, END_TIME - START_TIME
- def MATRIX_MULT(A, B):
- return np.dot(A, B)
- def MATRIX_POWER(M, POWER):
- RESULT = np.eye(len(M), dtype=int)
- BASE = M
- while POWER:
- if POWER % 2 == 1:
- RESULT = MATRIX_MULT(RESULT, BASE)
- BASE = MATRIX_MULT(BASE, BASE)
- POWER //= 2
- return RESULT
- def FIB_MATRIX(N):
- if N <= 1:
- return N
- F = np.array([[1, 1],
- [1, 0]])
- RESULT_MATRIX = MATRIX_POWER(F, N - 1)
- return RESULT_MATRIX[0, 0]
- def MEASURE_TIME_FIB_MATRIX(N):
- START_TIME = time.time()
- RESULT = FIB_MATRIX(N)
- END_TIME = time.time()
- return RESULT, END_TIME - START_TIME
- def MATRIX_MULT_THREAD(A, B):
- with ThreadPoolExecutor() as executor:
- FUTURES = [executor.submit(np.dot, A, B)]
- RESULT = [future.result() for future in FUTURES][0]
- return RESULT
- def MATRIX_POWER_THREAD(M, POWER):
- RESULT = np.eye(len(M), dtype=int)
- BASE = M
- while POWER:
- if POWER % 2 == 1:
- RESULT = MATRIX_MULT_THREAD(RESULT, BASE)
- BASE = MATRIX_MULT_THREAD(BASE, BASE)
- POWER //= 2
- return RESULT
- def FIB_MATRIX_THREAD(N):
- if N <= 1:
- return N
- F = np.array([[1, 1],
- [1, 0]])
- RESULT_MATRIX = MATRIX_POWER_THREAD(F, N - 1)
- return RESULT_MATRIX[0, 0]
- if __name__ == "__main__":
- N = 50
- print("starting naive")
- RESULT, ELAPSED_TIME = MEASURE_TIME_FIB(N)
- print(f"{RESULT}")
- print(f"{ELAPSED_TIME:.6f} sec")
- print("\nstarting matrix-based fibonacci (Multithreaded):")
- START_TIME = time.time()
- RESULT = FIB_MATRIX_THREAD(N)
- END_TIME = time.time()
- print(f"{RESULT}")
- print(f"{END_TIME - START_TIME:.6f} sec")
Advertisement
Add Comment
Please, Sign In to add comment