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
Top comments (2)
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:
Explanation here
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.
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.