Guest User

Fib Matrix Threading

a guest
Aug 3rd, 2024
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.07 KB | None | 0 0
  1. import time
  2. import numpy as np
  3. from concurrent.futures import ThreadPoolExecutor
  4.  
  5. def FIB(N):
  6. if N <= 1:
  7. return N
  8. else:
  9. return FIB(N - 1) + FIB(N - 2)
  10.  
  11. def MEASURE_TIME_FIB(N):
  12. START_TIME = time.time()
  13. RESULT = FIB(N)
  14. END_TIME = time.time()
  15. return RESULT, END_TIME - START_TIME
  16.  
  17. def MATRIX_MULT(A, B):
  18. return np.dot(A, B)
  19.  
  20. def MATRIX_POWER(M, POWER):
  21. RESULT = np.eye(len(M), dtype=int)
  22. BASE = M
  23.  
  24. while POWER:
  25. if POWER % 2 == 1:
  26. RESULT = MATRIX_MULT(RESULT, BASE)
  27. BASE = MATRIX_MULT(BASE, BASE)
  28. POWER //= 2
  29.  
  30. return RESULT
  31.  
  32. def FIB_MATRIX(N):
  33. if N <= 1:
  34. return N
  35.  
  36. F = np.array([[1, 1],
  37. [1, 0]])
  38.  
  39. RESULT_MATRIX = MATRIX_POWER(F, N - 1)
  40.  
  41. return RESULT_MATRIX[0, 0]
  42.  
  43. def MEASURE_TIME_FIB_MATRIX(N):
  44. START_TIME = time.time()
  45. RESULT = FIB_MATRIX(N)
  46. END_TIME = time.time()
  47. return RESULT, END_TIME - START_TIME
  48.  
  49. def MATRIX_MULT_THREAD(A, B):
  50. with ThreadPoolExecutor() as executor:
  51. FUTURES = [executor.submit(np.dot, A, B)]
  52. RESULT = [future.result() for future in FUTURES][0]
  53. return RESULT
  54.  
  55. def MATRIX_POWER_THREAD(M, POWER):
  56. RESULT = np.eye(len(M), dtype=int)
  57. BASE = M
  58.  
  59. while POWER:
  60. if POWER % 2 == 1:
  61. RESULT = MATRIX_MULT_THREAD(RESULT, BASE)
  62. BASE = MATRIX_MULT_THREAD(BASE, BASE)
  63. POWER //= 2
  64.  
  65. return RESULT
  66.  
  67. def FIB_MATRIX_THREAD(N):
  68. if N <= 1:
  69. return N
  70.  
  71. F = np.array([[1, 1],
  72. [1, 0]])
  73.  
  74. RESULT_MATRIX = MATRIX_POWER_THREAD(F, N - 1)
  75.  
  76. return RESULT_MATRIX[0, 0]
  77.  
  78. if __name__ == "__main__":
  79. N = 50
  80.  
  81. print("starting naive")
  82. RESULT, ELAPSED_TIME = MEASURE_TIME_FIB(N)
  83. print(f"{RESULT}")
  84. print(f"{ELAPSED_TIME:.6f} sec")
  85.  
  86. print("\nstarting matrix-based fibonacci (Multithreaded):")
  87. START_TIME = time.time()
  88. RESULT = FIB_MATRIX_THREAD(N)
  89. END_TIME = time.time()
  90. print(f"{RESULT}")
  91. print(f"{END_TIME - START_TIME:.6f} sec")
  92.  
Advertisement
Add Comment
Please, Sign In to add comment