import time
from functools import lru_cache

import numpy as np
from matplotlib import pyplot as plt
from decimal import Decimal, getcontext


getcontext().prec = 250


def fib_binet(n):
    sqrt5 = Decimal(5) ** Decimal('0.5')
    golden_ratio = (1 + sqrt5) / Decimal(2)
    golden_ratio_alt = (1 - sqrt5) / Decimal(2)
    return round((golden_ratio ** Decimal(n) - golden_ratio_alt ** Decimal(n)) / sqrt5)


def fib_fast_double(n):
    def recursive(n):
        if n == 0:
            return 1, 0
        
        q, r = divmod(n, 2)
        f2, f1 = recursive(q)
        f2, f1 = f1 ** 2 + f2 ** 2, f1 * (2 * f2 - f1)
        if r == 0:
            return f2, f1
        return f1 + f2, f2
    return recursive(n)[1]


def fib_fast_double_iter(n):
    tracker = []

    while n > 1:
        tracker.append(n)
        n //= 2

    f1, f2 = 1, 1

    while tracker:
        n = tracker.pop()
        f1, f2 = f1 * (2 * f2 - f1), f1 ** 2 + f2 ** 2
        if n % 2 == 1:
            f1, f2 = f2, f1 + f2
    return f1


def fib_matrix(n):
    A = [[1, 1], [1, 0]]
            
    def power(A, n):
        if n < 2:
            return A
        q, r = divmod(n, 2)
        power(A, q)
        multiply(A, A)
        if r != 0:
            multiply(A, [[1, 1], [1, 0]])
            
    def multiply(A, B):
        x = A[0][0] * B[0][0] + A[0][1] * B[1][0]
        y = A[0][0] * B[0][1] + A[0][1] * B[1][1]
        z = A[1][0] * B[0][0] + A[1][1] * B[1][0]
        w = A[1][0] * B[0][1] + A[1][1] * B[1][1]

        A[0][0] = x
        A[0][1] = y
        A[1][0] = z
        A[1][1] = w

    power(A, n-1)
    return A[0][0]


def fib_iterative(n):
    f1, f2 = 1, 1
    for _ in range(2, n):  # 當 n < 3 時不會進入迴圈
        f1, f2 = f2, f1 + f2
    return f2


@lru_cache(maxsize=2)
def fib_lru(n):
    if n < 3:
        return 1
    return fib_lru(n-2) + fib_lru(n-1)

functions = [fib_binet, fib_fast_double, fib_fast_double_iter, fib_matrix, fib_iterative, fib_lru]

# unittest
for i in [1, 10, 100, 1000]:
    res = []
    for f in functions:
        res.append(f(i))
    assert all(x == res[0] for x in res[1:])

# time measurement
xx = list(range(10, 1001, 20))
repeat = 1000

res = []
for i in xx:
    for j in range(repeat):
        res_j = [0 for _ in range(len(functions))]
        for k, f in enumerate(functions):
            time1 = time.time()
            f(i)
            time2 = time.time()
            res_j[k] += time2 - time1
            if f.__name__ == 'fib_lru':
                f.cache_clear()

    res.append(res_j)
res = np.array(res).T * 1000

# plot
for k, f in enumerate(functions):
    plt.plot(xx, res[k], label=f.__name__)

plt.legend()
plt.xlabel('n')
plt.ylabel('time/1000 run (ms)')
plt.savefig('res.png')