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