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

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

Comments

[Jon Randy 🎖️]

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

Explanation here

[mengqinyuan]

Thank you for your explanation . Yes, and I mentioned it in the article.

But how can we calculate like : 1,3,4,7,11.....
Here's the solution :

Defining the Sequence
Given the initial values (G_0 = a) and (G_1 = b), the recursive relation for the sequence is: [ G_n = G_{n-1} + G_{n-2} ]

Closed-Form Expression
For the generalized Fibonacci sequence (G_n), we can find a similar closed-form expression. Assuming the initial values are (G_0 = a) and (G_1 = b), the (n)th term (G_n) can be expressed as: [ G_n = A\varphi^n + B(1-\varphi)^n ]

where (\varphi = \frac{1 + \sqrt{5}}{2}) is the golden ratio, and (A) and (B) are coefficients determined by the initial values (a) and (b).

Solving for (A) and (B)
To find the values of (A) and (B), we use the initial conditions:

When (n = 0), (G_0 = A\varphi^0 + B(1-\varphi)^0 = A + B = a)
When (n = 1), (G_1 = A\varphi^1 + B(1-\varphi)^1 = A\varphi + B(1-\varphi) = b)
By solving this system of linear equations, we can determine the values of (A) and (B).

Example
For the given sequence with (G_0 = a) and (G_1 = b), we solve the system of equations to find (A) and (B):

(A + B = a)
(A\varphi + B(1-\varphi) = b)
Solving this system gives us the values of (A) and (B), which in turn give us the closed-form expression for the sequence.

Python Implementation
We can use Python to compute the values of (A) and (B), and then use these values to calculate the (n)th term of the sequence.

import math

def generalized_fibonacci(n, a, b):
    phi = (1 + math.sqrt(5)) / 2
    psi = (1 - math.sqrt(5)) / 2

    # Solve the system of equations for A and B
    A = (b - a * psi) / math.sqrt(5)
    B = (a * phi - b) / math.sqrt(5)

    # Use the closed-form expression to calculate the nth term
    return int(A * (phi ** n) + B * (psi ** n))

# Test
a = 1
b = 3
print(generalized_fibonacci(0, a, b))  # Should output 1
print(generalized_fibonacci(1, a, b))  # Should output 3
print(generalized_fibonacci(2, a, b))  # Should output 4
print(generalized_fibonacci(3, a, b))  # Should output 7
print(generalized_fibonacci(4, a, b))  # Should output 11

This code defines a function generalized_fibonacci that takes an integer n, and the initial values a and b, and returns the (n)th term of the sequence. You can run this code to verify that the results match your expectations.