How Far Can You Optimize a Program to Compute the Fibonacci Sequence?

Introduction

When I was learning Python, our teacher gave us a homework -- calculate the Nth number of Fibonacci Sequence.

I think it's very easy, so I write this code:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

Later, I know this kind of solution cost too much time.

When you read here, you may think of the Binet, but we need to consider the float problems.

$$ [ F(n) = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right) ] $$

Optimize a Program

I change the solution to iteration.

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1]+ls[i-2])

    return ls[n-1]

I use matplotlib draw the time it cost:

import time
import matplotlib.pyplot as plt


def bench_mark(func, *args):
    # calculate the time
    start = time.perf_counter()
    result = func(*args)
    end = time.perf_counter()

    return end - start, result  # return the time and the result

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1]+ls[i-2])

    return ls[n-1]

mark_list = []

for i in range(1,10000):
    mark = bench_mark(fib,i)
    mark_list.append(mark[0])
    print(f"size : {i} , time : {mark[0]}")

plt.plot(range(1, 10000), mark_list)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (seconds)')
plt.title('Test fot fibonacci')
plt.grid(True)
plt.show()

Here is the result:

The time it cost is very short.

But I write fib(300000), cost 5.719049899998936 seconds. It's too long.

When I grow up, I learn CACHE, so I change the solution to use dict to store the result.

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

Or we can write the CACHE by ourself.

def fib(n, cache={}):
    if n in cache:
        return cache[n]
    elif n < 2:
        return 1
    else:
        ls = [1, 1]
        for i in range(2, n):
            next_value = ls[-1] + ls[-2]
            ls.append(next_value)
            cache[i] = next_value
        cache[n-1] = ls[-1]
        return ls[-1]

I compare two kinds of fib with cache, and one without cache:

from functools import lru_cache
import matplotlib.pyplot as plt
import sys
sys.set_int_max_str_digits(7500)
sys.setrecursionlimit(190000)
@lru_cache(maxsize=None)
def fib_with_lru_cache(n):
    if n < 2:
        return 1
    else:
        return fib_with_lru_cache(n - 1) + fib_with_lru_cache(n - 2)

def fib_with_hand_writing_cache(n, cache={}):
    if n in cache:
        return cache[n]
    elif n < 2:
        return 1
    else:
        ls = [1, 1]
        for i in range(2, n):
            next_value = ls[-1] + ls[-2]
            ls.append(next_value)
            cache[i] = next_value
        cache[n-1] = ls[-1]
        return ls[-1]

def fib_with_no_cache(n) :
    ls = [1, 1]
    for i in range(2, n):
        next_value = ls[-1] + ls[-2]
        ls.append(next_value)
    return ls[-1]

def bench_mark(func, *args):
    import time
    start = time.perf_counter()
    func(*args)
    end = time.perf_counter()
    print(f'{func.__name__} took {end - start} seconds to run.')
    return end - start

lru_cache_time = []
hand_writing_cache_time = []
no_cache_time = []
for i in range(1, 18000):
    lru_cache_time.append(bench_mark(fib_with_lru_cache, i))
    hand_writing_cache_time.append(bench_mark(fib_with_hand_writing_cache, i))
    no_cache_time.append(bench_mark(fib_with_no_cache, i))

plt.plot(lru_cache_time, label='lru_cache')
plt.plot(hand_writing_cache_time, label='hand_writing_cache')
plt.plot(no_cache_time, label='no_cache')
plt.legend()
plt.show()

I calculate from fib(1) to fib(18000) in order to see the difference clearly.

Here is the result:

Later, I know the MATRIX EXPONENTIAL, so I change the solution to use matrix.
Here is the code:


def matrix_power(matrix, power):
    if power == 1:
        return matrix
    elif power % 2 == 0:
        half_power = matrix_power(matrix, power // 2)
        return matrix_multiply(half_power, half_power)
    else:
        return matrix_multiply(matrix, matrix_power(matrix, power - 1))

def matrix_multiply(a, b):
    a11, a12, a21, a22 = a
    b11, b12, b21, b22 = b
    return (
        a11 * b11 + a12 * b21,
        a11 * b12 + a12 * b22,
        a21 * b11 + a22 * b21,
        a21 * b12 + a22 * b22
    )

def fibonacci(n):
    if n <= 1:
        return n
    fib_matrix = (1, 1, 1, 0)
    result_matrix = matrix_power(fib_matrix, n - 1)
    return result_matrix[0] + result_matrix[2]

I make the compare with the previous solution:

What is the next step?

There are many kinds of solution to solve this problem. I think the next step is to learn more about the algorithm.
And do not give up finding the solution. Maybe you can have more ideas.

Additional

A person named "Jon Randy 🎖️" add my idea, here is the reply :

JS function to calculate Nth Fibonacci number in O(1) - well, maybe O(log N) - depends on how the system implements some of the underlying maths functions:


const fibonacci = n => {
  const r5 = 5**.5
  return Math.floor((((1+r5)/2)**n - ((1-r5)/2)**n)/r5)
}

And HE/SHE gives a explanation (very detailed) :
https://akuli.github.io/math-tutorial/fib.html

End

My Github : https://github.com/mengqinyuan
My Dev.to : https://dev.to/mengqinyuan

How Far You Can Optimize a Program to Compute the Fibonacci Sequence?

How Far Can You Optimize a Program to Compute the Fibonacci Sequence?

Introduction

Optimize a Program

What is the next step?

Additional

End