Skip to content

Instantly share code, notes, and snippets.

@dwy6626

dwy6626/fibonacci.py

Last active December 21, 2022 12:01
Show Gist options
  • Save dwy6626/ca70c57da3b79daae1bd8df05e98d0c2 to your computer and use it in GitHub Desktop.
Save dwy6626/ca70c57da3b79daae1bd8df05e98d0c2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. dwy6626 revised this gist May 31, 2021. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -10,7 +10,7 @@


    def fib_binet(n):
    sqrt5 = Decimal(5) ** Decimal(0.5)
    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)
  2. dwy6626 revised this gist May 28, 2021. 1 changed file with 10 additions and 19 deletions.
    29 changes: 10 additions & 19 deletions fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -3,12 +3,17 @@

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


    getcontext().prec = 250


    def fib_binet(n):
    golden_ratio = (1 + 5 ** 0.5) / 2
    golden_ratio_alt = (1 - 5 ** 0.5) / 2
    return int((golden_ratio ** n - golden_ratio_alt ** n) / 5 ** 0.5)
    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):
    @@ -69,11 +74,6 @@ def multiply(A, B):
    return A[0][0]


    def fib_numpy(n):
    A = np.array([[1, 1], [1, 0]])
    return np.linalg.matrix_power(A, n-1)[0, 0]


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


    def fib_tail_recursive(n):
    def tr(n, f1, f2):
    if n < 3:
    return f2
    return tr(n - 1, f2, f1 + f2)
    return tr(n, 1, 1)

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

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

    # unittest
    for i in range(1, 30):
    for i in [1, 10, 100, 1000]:
    res = []
    for f in functions:
    res.append(f(i))
  3. dwy6626 revised this gist May 9, 2021. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -7,7 +7,8 @@

    def fib_binet(n):
    golden_ratio = (1 + 5 ** 0.5) / 2
    return int((golden_ratio ** n + 1) / 5 ** 0.5)
    golden_ratio_alt = (1 - 5 ** 0.5) / 2
    return int((golden_ratio ** n - golden_ratio_alt ** n) / 5 ** 0.5)


    def fib_fast_double(n):
  4. dwy6626 revised this gist Apr 4, 2021. 1 changed file with 9 additions and 0 deletions.
    9 changes: 9 additions & 0 deletions fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -4,10 +4,12 @@
    import numpy as np
    from matplotlib import pyplot as plt


    def fib_binet(n):
    golden_ratio = (1 + 5 ** 0.5) / 2
    return int((golden_ratio ** n + 1) / 5 ** 0.5)


    def fib_fast_double(n):
    def recursive(n):
    if n == 0:
    @@ -65,22 +67,26 @@ def multiply(A, B):
    power(A, n-1)
    return A[0][0]


    def fib_numpy(n):
    A = np.array([[1, 1], [1, 0]])
    return np.linalg.matrix_power(A, n-1)[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)


    def fib_tail_recursive(n):
    def tr(n, f1, f2):
    if n < 3:
    @@ -90,13 +96,15 @@ def tr(n, f1, f2):

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


    # unittest
    for i in range(1, 30):
    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

    @@ -115,6 +123,7 @@ def tr(n, f1, f2):
    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__)

  5. dwy6626 revised this gist Apr 4, 2021. 1 changed file with 48 additions and 24 deletions.
    72 changes: 48 additions & 24 deletions fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,4 @@
    import timeit
    import time
    from functools import lru_cache

    import numpy as np
    @@ -21,6 +21,24 @@ def recursive(n):
    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]]

    @@ -70,31 +88,37 @@ def tr(n, f1, f2):
    return tr(n - 1, f2, f1 + f2)
    return tr(n, 1, 1)

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

    # unittest
    for i in range(1, 30):
    assert fib_matrix(i) == fib_numpy(i) == fib_iterative(i) == fib_lru(i) == fib_tail_recursive(i) == fib_fast_double(i) == fib_binet(i)

    xx = list(range(10, 501, 10))
    res = [(
    timeit.timeit(lambda: fib_matrix(i), number=100),
    timeit.timeit(lambda: fib_numpy(i), number=100),
    timeit.timeit(lambda: fib_iterative(i), number=100),
    sum((
    timeit.timeit(lambda: fib_lru(i), setup=lambda: fib_lru.cache_clear(), number=1) for _ in range(100)
    )),
    timeit.timeit(lambda: fib_tail_recursive(i), number=100),
    timeit.timeit(lambda: fib_fast_double(i), number=100),
    timeit.timeit(lambda: fib_binet(i), number=100),
    ) for i in xx]
    res = []
    for f in functions:
    res.append(f(i))
    assert all(x == res[0] for x in res[1:])

    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

    plt.plot(xx, res[0], label='naive matrix')
    plt.plot(xx, res[1], label='numpy')
    plt.plot(xx, res[2], label='iterative')
    plt.plot(xx, res[3], label='recursive with lru cache')
    plt.plot(xx, res[4], label='tail recursive')
    plt.plot(xx, res[5], label='fast double')
    plt.plot(xx, res[6], label='Binet\'s formula')
    for k, f in enumerate(functions):
    plt.plot(xx, res[k], label=f.__name__)

    plt.legend()
    plt.xlabel('n')
    plt.ylabel('time/100 run (ms)')
    plt.show()
    plt.ylabel('time/1000 run (ms)')
    plt.savefig('res.png')
  6. dwy6626 revised this gist Mar 31, 2021. 1 changed file with 25 additions and 10 deletions.
    35 changes: 25 additions & 10 deletions fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -4,10 +4,24 @@
    import numpy as np
    from matplotlib import pyplot as plt

    def fib_matrix(n):
    if n < 3:
    return 1
    def fib_binet(n):
    golden_ratio = (1 + 5 ** 0.5) / 2
    return int((golden_ratio ** n + 1) / 5 ** 0.5)

    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_matrix(n):
    A = [[1, 1], [1, 0]]

    def power(A, n):
    @@ -34,15 +48,12 @@ def multiply(A, B):
    return A[0][0]

    def fib_numpy(n):
    if n < 3:
    return 1

    A = np.array([[1, 1], [1, 0]])
    return np.linalg.matrix_power(A, n-1)[0, 0]

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

    @@ -59,10 +70,10 @@ def tr(n, f1, f2):
    return tr(n - 1, f2, f1 + f2)
    return tr(n, 1, 1)

    for i in range(30):
    assert fib_matrix(i) == fib_numpy(i) == fib_iterative(i) == fib_lru(i) == fib_tail_recursive(i)
    for i in range(1, 30):
    assert fib_matrix(i) == fib_numpy(i) == fib_iterative(i) == fib_lru(i) == fib_tail_recursive(i) == fib_fast_double(i) == fib_binet(i)

    xx = list(range(10, 151, 10))
    xx = list(range(10, 501, 10))
    res = [(
    timeit.timeit(lambda: fib_matrix(i), number=100),
    timeit.timeit(lambda: fib_numpy(i), number=100),
    @@ -71,6 +82,8 @@ def tr(n, f1, f2):
    timeit.timeit(lambda: fib_lru(i), setup=lambda: fib_lru.cache_clear(), number=1) for _ in range(100)
    )),
    timeit.timeit(lambda: fib_tail_recursive(i), number=100),
    timeit.timeit(lambda: fib_fast_double(i), number=100),
    timeit.timeit(lambda: fib_binet(i), number=100),
    ) for i in xx]
    res = np.array(res).T * 1000

    @@ -79,6 +92,8 @@ def tr(n, f1, f2):
    plt.plot(xx, res[2], label='iterative')
    plt.plot(xx, res[3], label='recursive with lru cache')
    plt.plot(xx, res[4], label='tail recursive')
    plt.plot(xx, res[5], label='fast double')
    plt.plot(xx, res[6], label='Binet\'s formula')
    plt.legend()
    plt.xlabel('n')
    plt.ylabel('time/100 run (ms)')
  7. dwy6626 revised this gist Mar 28, 2021. 1 changed file with 19 additions and 16 deletions.
    35 changes: 19 additions & 16 deletions fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,7 @@
    import numpy as np
    from matplotlib import pyplot as plt

    def fib1(n: int) -> int:
    def fib_matrix(n):
    if n < 3:
    return 1

    @@ -33,41 +33,44 @@ def multiply(A, B):
    power(A, n-1)
    return A[0][0]

    def fib2(n: int) -> int:
    def fib_numpy(n):
    if n < 3:
    return 1

    A = np.array([[1, 1], [1, 0]]) ** (n-1)
    return A[0, 0]
    A = np.array([[1, 1], [1, 0]])
    return np.linalg.matrix_power(A, n-1)[0, 0]

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

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

    def fib5(n):
    def fib_tail_recursive(n, f1, f2):
    def fib_tail_recursive(n):
    def tr(n, f1, f2):
    if n < 3:
    return f2
    return fib_tail_recursive(n - 1, f2, f1 + f2)
    return fib_tail_recursive(n, 1, 1)
    return tr(n - 1, f2, f1 + f2)
    return tr(n, 1, 1)

    for i in range(30):
    assert fib_matrix(i) == fib_numpy(i) == fib_iterative(i) == fib_lru(i) == fib_tail_recursive(i)

    xx = list(range(10, 151, 10))
    res = [(
    timeit.timeit(lambda: fib1(i), number=100),
    timeit.timeit(lambda: fib2(i), number=100),
    timeit.timeit(lambda: fib3(i), number=100),
    timeit.timeit(lambda: fib_matrix(i), number=100),
    timeit.timeit(lambda: fib_numpy(i), number=100),
    timeit.timeit(lambda: fib_iterative(i), number=100),
    sum((
    timeit.timeit(lambda: fib4(i), setup=lambda: fib4.cache_clear(), number=1) for _ in range(100)
    timeit.timeit(lambda: fib_lru(i), setup=lambda: fib_lru.cache_clear(), number=1) for _ in range(100)
    )),
    timeit.timeit(lambda: fib5(i), number=100),
    timeit.timeit(lambda: fib_tail_recursive(i), number=100),
    ) for i in xx]
    res = np.array(res).T * 1000

  8. dwy6626 created this gist Mar 28, 2021.
    82 changes: 82 additions & 0 deletions fibonacci.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,82 @@
    import timeit
    from functools import lru_cache

    import numpy as np
    from matplotlib import pyplot as plt

    def fib1(n: int) -> int:
    if n < 3:
    return 1

    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 fib2(n: int) -> int:
    if n < 3:
    return 1

    A = np.array([[1, 1], [1, 0]]) ** (n-1)
    return A[0, 0]

    def fib3(n: int) -> int:
    f1, f2 = 1, 1
    for i in range(2, n): # 當 n < 3 時不會進入迴圈
    f1, f2 = f2, f1 + f2
    return f2

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

    def fib5(n):
    def fib_tail_recursive(n, f1, f2):
    if n < 3:
    return f2
    return fib_tail_recursive(n - 1, f2, f1 + f2)
    return fib_tail_recursive(n, 1, 1)

    xx = list(range(10, 151, 10))
    res = [(
    timeit.timeit(lambda: fib1(i), number=100),
    timeit.timeit(lambda: fib2(i), number=100),
    timeit.timeit(lambda: fib3(i), number=100),
    sum((
    timeit.timeit(lambda: fib4(i), setup=lambda: fib4.cache_clear(), number=1) for _ in range(100)
    )),
    timeit.timeit(lambda: fib5(i), number=100),
    ) for i in xx]
    res = np.array(res).T * 1000

    plt.plot(xx, res[0], label='naive matrix')
    plt.plot(xx, res[1], label='numpy')
    plt.plot(xx, res[2], label='iterative')
    plt.plot(xx, res[3], label='recursive with lru cache')
    plt.plot(xx, res[4], label='tail recursive')
    plt.legend()
    plt.xlabel('n')
    plt.ylabel('time/100 run (ms)')
    plt.show()