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")